#include <bits/stdc++.h>
using namespace std;
#define pi pair<int,int>
#define pb push_back
const int mxn = 2e5+10;
vector<pi> g[mxn];
int n,k;
int sub[mxn];
bitset<mxn> vis;
int getsize(int u, int p){
sub[u] = 1;
for(auto [v,w] : g[u]) if(v!=p && !vis[v])
sub[u] += getsize(v,u);
return sub[u];
}
int getcen(int u, int p, int sz){
for(auto [v,w] : g[u]) if(v!=p && !vis[v])
if(sub[v]<<1 > sz) return getcen(v,u,sz);
return u;
}
map<int,int> mp;
int res = mxn;
void dfs1(int u, int p, int dis, int cnt){
if(dis>k) return;
if(mp.count(k-dis))
res = min(res,mp[k-dis]+cnt);
for(auto [v,w] : g[u]) if(v!=p && !vis[v])
dfs1(v,u,dis+w,cnt+1);
}
void dfs2(int u, int p, int dis, int cnt){
if(dis>k) return;
if(mp.count(dis))
mp[dis] = min(mp[dis],cnt);
else mp[dis] = cnt;
for(auto [v,w] : g[u]) if(v!=p && !vis[v])
dfs2(v,u,dis+w,cnt+1);
}
void centroid(int u){
u = getcen(u,u,getsize(u,u));
mp[0] = 0, vis[u] = 1;
for(auto [v,w] : g[u]) if(!vis[v]){
dfs1(v,u,w,1);
dfs2(v,u,w,1);
}
mp.clear();
for(auto [v,w] : g[u]) if(!vis[v])
centroid(u);
}
int best_path(int N, int K, int h[][2], int l[]){
n = N, k = K;
for(int i = 0; i < n-1; i++){
g[h[i][0]+1].pb({h[i][1]+1,l[i]});
g[h[i][1]+1].pb({h[i][0]+1,l[i]});
}
if(res==mxn) return -1;
return res;
}
