#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define INF (int)1000000005
typedef long long ll;
ll k;
int ans;
struct node{
map<ll,int> res;//(length,edges)
ll add_l;
int add_e;
node(){
res[0]=0;
add_l=add_e=0;
}
void merge(node n,ll w){
for(auto p:n.res){
ll l=p.first+n.add_l+w;
int e=p.second+n.add_e+1;
if(res.count(k-l-add_l)) ans=min(ans,res[k-l-add_l]+add_e+e);
}
for(auto p:n.res){
ll l=p.first+n.add_l+w-add_l;
int e=p.second+n.add_e+1-add_e;
if(res.count(l)) res[l]=min(res[l],e);
else res[l]=e;
}
}
void init_big(ll w){
add_e+=1;
add_l+=w;
res[-add_l]=-add_e;
if(res.count(k-add_l)) ans=min(ans,res[k-add_l]+add_e);
}
};
node arr[MAXN];
int rep[MAXN];
vector<pair<int,ll>> adj[MAXN];//(to,weight)
void dfs(int curr,int par=-1){
int big_c=-1;
ll w_big=0;
for(auto p:adj[curr]){
int to=p.first;
ll w=p.second;
if(to==par) continue;
dfs(to,curr);
if(big_c==-1||arr[rep[big_c]].res.size()<arr[rep[to]].res.size()){
big_c=to;
w_big=w;
}
}
if(big_c==-1){
rep[curr]=curr;
return;
}else{
rep[curr]=rep[big_c];
arr[rep[big_c]].init_big(w_big);
}
for(auto p:adj[curr]){
int to=p.first;
ll w=p.second;
if(to==par||to==big_c) continue;
arr[rep[big_c]].merge(arr[rep[to]],w);
rep[to]=rep[big_c];
}
}
int best_path(int N, int K, int H[][2], int L[])
{
ans=INF;
k=K;
for(int 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]});
}
dfs(0);
return ans==INF?-1:ans;
}
