#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
map<ll,int> se[maxn];
int dep[maxn];
int val[maxn];
vector<vector<pair<int,int>>> adj;
int ans = 1<<30, gK;
void dfs(int nod, int par){
se[nod][val[nod]] = dep[nod];
for(auto nxt : adj[nod]){
if(nxt.first == par)continue;
dep[nxt.first] = dep[nod]+1;
val[nxt.first] = val[nod]+nxt.second;
dfs(nxt.first,nod);
if(se[nod].size() < se[nxt.first].size())swap(se[nod], se[nxt.first]);
}
for(auto nxt : adj[nod]){
if(nxt.first == par)continue;
for(auto it : se[nxt.first]){
int missing = gK + 2*val[nod] - it.first;
if(se[nod][missing]){
ans = min(ans, it.second + se[nod][missing] - 2*dep[nod]);
}
}
for(auto it : se[nxt.first]){
if(se[nod][it.first])se[nod][it.first] = min(se[nod][it.first], it.second);
else se[nod][it.first] = it.second;
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
memset(dep,1,sizeof dep);
gK = K;
adj.resize(N);
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,0);
if(ans == (1<<30))return -1;
return ans;
}
