#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> adj[200001];
ll sz[200001];
bool marked[200001]={0};
ll k;
ll dfs_sizes(ll v, ll pV){
sz[v]=0;
for(auto [w,d] : adj[v]){
if(w!=pV&&!marked[w]){
sz[v]+=dfs_sizes(w,v);
}
}
return sz[v];
}
ll dfs_centroid(ll v, ll pV, ll subtree_sz){
for(auto [w,d] : adj[v]){
if(pV!=w&&!marked[w]&&sz[w]>=(subtree_sz/2)){
return dfs_centroid(w,v,subtree_sz);
}
}
return v;
}
void dfs_paths(ll v, ll pV,ll dist,ll l, vector<pair<ll,ll>> &a){
for(auto [w,d] : adj[v]){
if(w!=pV&&!marked[w]){
if(dist+d<=1000000){
a.push_back({dist+d,l+1});
dfs_paths(w,v,dist+d,l+1,a);
}
}
}
}
map<ll,ll> m;
vector<pair<ll,ll>> a;
ll centroid_decomposition(ll v){
ll c = dfs_centroid(v,v,dfs_sizes(v,v));
marked[c]=1;
ll ans=1000001;
m = map<ll,ll>();
m[0]=0;
for(auto [w,d] : adj[c]){
if(!marked[w]){
a.resize(0);
dfs_paths(w,c,d,1,a);
for(auto [dist,l] : a){
if(m.count(k-dist)){
ans=min(ans,l+m[k-dist]);
}
}
for(auto [dist,l] : a){
if(m.count(dist))m[dist]=min(m[dist],l);
else m[dist]=l;
}
}
}
for(auto [w,d] : adj[c]){
if(!marked[w]){
ans = min(ans,centroid_decomposition(w));
}
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
for(ll i=0;i<N-1;i++){
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
k=K;
ll ans = centroid_decomposition(0);
return (ans==1000001?-1:ans);
}
