#include <bits/stdc++.h>
using namespace std;
int const MN=200005;
map<int,int> cnt;
vector<pair<int,int>> adj[MN];
int sz[MN];
int n,k;
int ans=MN;
void dfs_sz(int node,int par=-1){
sz[node]=1;
for(auto i:adj[node])
if(i.first!=par){
dfs_sz(i.first,node);
sz[node]+=sz[i.first];
}
}
int total=0;
int find_centroid(int node){
for(auto i:adj[node]){
if(sz[i.first]*2>total){
sz[node]-=sz[i.first];
sz[i.first]+=sz[node];
return find_centroid(i.first);
}
}
return node;
}
void dfs(int node,int par,int w,int dep){
if(w==k)
ans=min(ans,dep);
if(w>=k)
return;
if(cnt.find(k-w)!=cnt.end())
ans=min(ans,cnt[k-w]+dep);
for(auto i:adj[node])
if(sz[i.first]!=-1 && i.first!=par)
dfs(i.first,node,w+i.second,dep+1);
}
void update(int node,int par,int w,int dep){
if(w>=k)
return;
if(cnt[w]==0 || cnt[w]>dep)
cnt[w]=dep;
for(auto i:adj[node])
if(sz[i.first]!=-1 && i.first!=par)
update(i.first,node,w+i.second,dep+1);
}
void solve(int node){
total=sz[node];
node=find_centroid(node);
sz[node]=-1;
// cout<<node<<endl;
for(auto i:adj[node]){
if(sz[i.first]==-1)
continue;
dfs(i.first,-1,i.second,1);
update(i.first,-1,i.second,1);
}
cnt.clear();
// cout<<ans<<endl;
for(auto i:adj[node])
if(sz[i.first]!=-1)
solve(i.first);
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;
k=K;
total=n;
for (int i = 0; i < n-1; ++i)
{
int u=H[i][0];
int v=H[i][1];
adj[u].push_back({v,L[i]});
adj[v].push_back({u,L[i]});
}
dfs_sz(0);
solve(0);
if(ans==MN)
ans=-1;
return ans;
}
