#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int maxn = 200005;
const int maxk = 1000005;
int sz[maxn], rem[maxn], length[maxk]{0};
vector<pair<int,int>> adj[maxn];
int N, K, ans;
int get_sz(int v, int p=-1){
sz[v] = 1;
for(auto [u, w]: adj[v]){
if(u == p || rem[u]) continue;
sz[v] += get_sz(u, v);
}
return sz[v];
}
int get_centroid(int tsz, int v, int p=-1){
for(auto [u, w]: adj[v]){
if(u == p || rem[u]) continue;
if(2 * sz[u] > tsz)
return get_centroid(tsz, u, v);
}
return v;
}
void dfs(int v, int p, int w, int d, int filling){
if(w > K) return;
if(filling == 1) length[w] = min(length[w], d);
if(filling == -1) length[w] = inf;
if(filling == 0) ans = min(ans, length[K-w] + d);
for(auto [u, nw]: adj[v]){
if(u == p || rem[u]) continue;
dfs(u, v, w+nw, d+1, filling);
}
}
void centroid_decomp(int v){
int centroid = get_centroid(get_sz(v), v);
rem[centroid] = true;
for(auto [u, w]: adj[centroid]){
if(rem[u]) continue;
dfs(u, centroid, w, 1, 0);
dfs(u, centroid, w, 1, 1);
}
for(auto [u, w]: adj[centroid]){
if(rem[u]) continue;
dfs(u, centroid, w, 1, -1);
centroid_decomp(u);
}
}
int best_path(int NN, int KK, int H[][2], int L[]){
N=NN, K=KK;
for(int i=0; i<N-1; i++){
int u=H[i][0], v=H[i][1];
adj[u].push_back(make_pair(v, L[i]));
adj[v].push_back(make_pair(u, L[i]));
}
fill(length+1, length+maxk, inf);
ans = inf;
centroid_decomp(0);
if(ans == inf) ans = -1;
return ans;
}
