#include<iostream>
#include "race.h"
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
vector< pair<long long,long long> > v[200005];
long long numv[200005],nex,rs,k;
long long ans=1000000000000000000;
bool used[200005];
map<long long,long long> mp;
pair<long long,long long> pr[200005],nw[200005],r[200005];
long long numvr(long long vr,long long par)
{
if(used[vr]) return 0;
long long b=0;
for(long long i=0;i<v[vr].size();i++)
{
if(v[vr][i].first==par) continue;
b+=numvr(v[vr][i].first,vr);
}
return numv[vr]=b+1;
}
long long findcen(long long vr,long long par,long long ncom)
{
if(used[vr]) return vr;
for(long long i=0;i<v[vr].size();i++)
{
if(v[vr][i].first==par) continue;
if(numv[v[vr][i].first]>(ncom/2)) return findcen(v[vr][i].first,vr,ncom);
}
return vr;
}
void finp(long long vr,long long par,long long d,long long br)
{
if(used[vr]) return;
nw[nex]={d,br};
nex++;
for(long long i=0;i<v[vr].size();i++)
{
if(v[vr][i].first!=par)
finp(v[vr][i].first,vr,v[vr][i].second+d,br+1);
}
}
void calc()
{
int tr;
for(int i=0;i<nex;i++)
{
if(mp.count(k-nw[i].first))
ans=min(ans,(mp[k-nw[i].first]+nw[i].second));
}
for(int i=0;i<nex;i++)
{
if(mp.count(nw[i].first))
mp[nw[i].first]=min(mp[nw[i].first],nw[i].second);
else
mp[nw[i].first]=nw[i].second;
}
}
void solve(long long cen)
{
if(used[cen]) return;
mp.clear();
nex=0;
pr[0]={0,0};
used[cen]=1;
for(long long i=0;i<v[cen].size();i++)
{
if(used[v[cen][i].first]) continue;
nex=0;
finp(v[cen][i].first,cen,v[cen][i].second,1);
calc();
}
for(long long i=0;i<v[cen].size();i++)
{
if(used[v[cen][i].first]) continue;
long long tn=numvr(v[cen][i].first,cen);
solve(findcen(v[cen][i].first,cen,tn));
}
}
int best_path (int N, int K, int H[][2], int L[])
{
k=K;
for(long long i=0;i<N-1;i++)
{
v[H[i][0]].push_back({H[i][1],L[i]});
v[H[i][1]].push_back({H[i][0],L[i]});
}
long long tn=numvr(H[0][0],-1);
solve(findcen(H[0][0],-1,tn));
if(ans==1000000000000000000) return -1;
return ans;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/
