#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int rez;
long long K;
vector<pair<int,int>> con[200005];
unordered_map<long long,int> dp[200005];
int d[200005];
long long d2[200005];
void dfs(int nod, int par)
{
if(d2[nod]==K) rez = min(rez, d[nod]);
int maxc=-1,heavy=-1;
for(auto [adj,w]:con[nod])
{
if(adj==par)
continue;
d[adj] = d[nod] + 1;
d2[adj] = d2[nod] + w;
dfs(adj,nod);
if((int)dp[adj].size() > maxc)
maxc = dp[adj].size(), heavy=adj;
}
if(heavy==-1)
{
}
else
{
swap(dp[nod], dp[heavy]);
for(auto [adj,w]:con[nod])
{
if(adj==par || adj==heavy)
continue;
for(auto it:dp[adj])
{
rez = min(rez, it.second + dp[nod][K+2*d2[nod]-it.first] + 2*INF - 2*d[nod]);
///it.first + x - 2*d2[nod] = K
}
for(auto it:dp[adj])
if(it.first - d2[nod] <= K)
dp[nod][it.first] = min(dp[nod][it.first], it.second);
dp[adj].clear();
}
}
rez = min(rez, dp[nod][K+d2[nod]] + INF - d[nod]);
///x - d2[nod] = K
dp[nod][d2[nod]] = min(dp[nod][d2[nod]], d[nod] - INF);
}
int best_path(int N, int copK, int H[][2], int L[])
{
K = copK;
rez = N+2;
for(int i=0;i<N-1;i++)
{
con[H[i][0]].push_back({H[i][1],L[i]});
con[H[i][1]].push_back({H[i][0],L[i]});
}
dfs(0,-1);
if(rez==N+2)
rez=-1;
return rez;
}
