#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define re first
#define im second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ii> vii;
typedef set<ii> sii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define MAXN 200069
#define INF 314159265358979323
int ans=INF,k;
vii adj[MAXN];
int lazy_dist[MAXN], lazy_highways[MAXN];
map<int,int> min_dist[MAXN];
void dfs(int x, int p) {
min_dist[x][0]=0;
for(auto i: adj[x]) if(i.re!=p) {
dfs(i.re, x);
lazy_dist[i.re]+=i.im;
lazy_highways[i.re]++;
if(min_dist[i.re].size()>min_dist[x].size()) {
swap(min_dist[i.re], min_dist[x]);
swap(lazy_dist[i.re], lazy_dist[x]);
swap(lazy_highways[i.re], lazy_highways[x]);
}
for(auto it: min_dist[i.re]) {
int rem=k-it.re-lazy_dist[i.re]-lazy_dist[x];
if(min_dist[x].count(rem)) ans=min(ans, it.im+min_dist[x][rem]+lazy_highways[i.re]+lazy_highways[x]);
}
for(auto it: min_dist[i.re]) {
int insPt=it.re+lazy_dist[i.re]-lazy_dist[x], insV=it.im+lazy_highways[i.re]-lazy_highways[x];
if(min_dist[x].count(insPt)) min_dist[x][insPt]=min(min_dist[x][insPt],insV);
else min_dist[x][insPt]=insV;
}
}
}
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]) {
REP(i,0,N-1) {
adj[H[i][0]].pb(ii(H[i][1],L[i]));
adj[H[i][1]].pb(ii(H[i][0],L[i]));
}
k=K;
dfs(0,-1);
return ((ans==INF)?-1:ans);
}
