#include "race.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
const int MAXN=200005;
typedef pair<int,int> pii;
long long pref[MAXN];
vector<pii> adj[MAXN];
int depth[MAXN],KK,ans=1e9;
map<long long,int> subtree[MAXN];
void merge(int now,int nxt){
for(map<long long,int>::iterator it=subtree[nxt].begin();it!=subtree[nxt].end();++it){
if(subtree[now].count(it->first))subtree[now][it->first]=min(subtree[now][it->first],it->second);
else subtree[now][it->first]=it->second;
}
}
void dfs(int now,int par){
subtree[now][pref[now]]=depth[now];
//hitung semua pasangan node yang LCAnya now
for(auto nxt : adj[now]){
if(nxt.fi==par)continue;
depth[nxt.fi]=depth[now]+1;
pref[nxt.fi]=pref[now]+nxt.se;
dfs(nxt.fi,now);
if(subtree[now].size()<subtree[nxt.fi].size())subtree[now].swap(subtree[nxt.fi]);
}
for(auto nxt : adj[now]){
if(nxt.fi==par)continue;
for(map<long long,int>::iterator it=subtree[nxt.fi].begin();it!=subtree[nxt.fi].end();++it){
int sisa=KK+2*pref[now]-it->first;
if(subtree[now].count(sisa)){
ans=min(ans,it->second+subtree[now][sisa]-2*depth[now]);
}
}
merge(now,nxt.fi);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
KK=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,-1);
if(ans==1e9)ans=-1;
return ans;
}
