#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define sp ' '
#define nl '\n'
void sc(){}template<class T,class...A>void sc(T&t,A&...a){cin>>t,sc(a...);}
void pr(){}template<class T,class...A>void pr(T t,A...a){cout<<t,pr(a...);}
#define ms(x, y) memset(x, y, sizeof(x))
#define sz(x) (int)(x.size())
#define af(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
const int mod = 1e9 + 7, base = 131;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int MM = 2e5 + 5;
int M, w[MM], ans = INF; bool vis[MM];
vector<pii> adj[MM];
map<int, int> cnt, tmp;
void get_weight(int src, int par){
w[src] = 1;
for (auto v : adj[src]){
if (v.s == par || vis[v.s]) continue;
get_weight(v.s, src);
w[src] += w[v.s];
}
}
int get_cent(int src, int par, int wt){
for (auto v : adj[src]){
if (v.s == par || vis[v.s]) continue;
if (w[v.s] * 2 > wt) return get_cent(v.s, src, wt);
}
return src;
}
void proc_subtree(int src, int par, int d, int dep){
if (d > M) return;
if (d == M) ans = min(ans, dep);
if (!tmp.count(d)) tmp[d] = dep;
else tmp[d] = min(tmp[d], dep);
if (cnt.count(M - d)) ans = min(ans, cnt[M - d] + dep);
for (auto v : adj[src]){
if (v.s == par || vis[v.s]) continue;
proc_subtree(v.s, src, d + v.f, dep + 1);
}
}
void get_ans(int src){
cnt.clear();
for (auto v : adj[src]){
if (vis[v.s]) continue;
tmp.clear();
proc_subtree(v.s, src, v.f, 1);
for (auto m : tmp){
if (!cnt.count(m.f)) cnt[m.f] = m.s;
else cnt[m.f] = min(cnt[m.f], m.s);
}
}
}
void decomp(int src){
vis[src] = 1;
get_ans(src);
for (auto v : adj[src]){
if (vis[v.s]) continue;
get_weight(v.s, src);
decomp(get_cent(v.s, src, w[v.s]));
}
}
int best_path(int N, int K, int H[][2], int L[]){
M = K;
for (int i = 0; i < N - 1; i++){
int a = H[i][0], b = H[i][1], c = L[i];
adj[a].pb(mp(c, b)); adj[b].pb(mp(c, a));
}
get_weight(1, 1);
decomp(get_cent(1, 1, N));
return ans == INF ? -1 : ans;
}
