#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pll= pair<ll,ll>;
#define pb push_back
vector<pll> adj[200010];
bool hide[200010];
ll sz[200010],k,ans=1e9;
map<ll,ll> mp;
void plant(ll v , ll p = 0){
sz[v] = 1;
for(auto [u,w] : adj[v])
if(u != p && !hide[u]){
plant(u , v);
sz[v] += sz[u];
}
}
ll find_centroid(ll v , ll n , ll p = 0){
bool found = 1;
while(found){
found = 0;
for(auto [u,w] : adj[v])
if(u != p && !hide[u] && sz[u] * 2 > n){
found = 1;
p = v;
v = u;
break;
}
}
return v;
}
void dfs(ll v, ll x, ll h, ll p=0){
if(x<=k && mp.count(k-x)) ans=min(ans,h+mp[k-x]);
for(auto [u,w] : adj[v]) if(!hide[u] && u!=p) dfs(u,x+w,h+1,v);
}
void sfd(ll v, ll x, ll h, ll p=0){
if(x<=k && (!mp.count(x) || mp[x]>h)) mp[x]=h;
for(auto [u,w] : adj[v]) if(!hide[u] && u!=p) sfd(u,x+w,h+1,v);
}
void solve(ll v){
plant(v);
v = find_centroid(v , sz[v]);
hide[v] = 1;
mp.clear();
mp[0]=0;
for(auto [u,w] : adj[v]){
if(!hide[u]){
dfs(u,w,1);
sfd(u,w,1);
}
}
for(auto [u,w] : adj[v]) if(!hide[u]) solve(u);
}
int best_path(int N, int K, int H[][2], int L[]){
for(ll i=0; i<N-1; i++){
ll v=H[i][0]+1,u=H[i][1]+1;
adj[v].pb({u,L[i]});
adj[u].pb({v,L[i]});
}
k=K;
solve(1);
if(ans==1e9) ans=-1;
return ans;
}
