#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf=1000000009;
const long long MAXN=100009;
const long long MAXK=1000009;
vector<pair<int,int>> edg[MAXN];
long long pod[MAXN];
long long father[MAXN];
long long best[MAXK];
bool hasBeenCentr[MAXN];
long long k,ans=inf;
vector<pair<int,int>> v;
inline long long min1(long long a,long long b)
{
if(a>b)return b;
return a;
}
long long dfs(int curr,int f)
{
father[curr]=f;
pod[curr]=1;
for(auto i:edg[curr])
{
if(i.first==f||hasBeenCentr[i.first])continue;
pod[curr]+=dfs(i.first,curr);
}
return pod[curr];
}
long long centr(int curr,int sz)
{
for(auto i:edg[curr])
{
if(i.first==father[curr]||hasBeenCentr[i.first])continue;
if(pod[i.first]>sz/2)return centr(i.first,sz);
}
return curr;
}
void dfsDist(int curr,int dist,int dept,int f)
{
v.push_back({dist,dept});
ans=min1(ans,dept+best[k-dist]);
for(auto i:edg[curr])
{
if(i.first==f||hasBeenCentr[i.first])continue;
dfsDist(i.first,dist+i.second,dept+1,curr);
}
}
void centrDec(int curr)
{
dfs(curr,-1);
v.clear();
int cen=centr(curr,pod[curr]);
for(int i=0;i<MAXK;i++)best[i]=inf;
best[0]=0;
for(auto i:edg[cen])
{
if(hasBeenCentr[i.first])continue;
dfsDist(i.first,0,1,curr);
for(auto t:v)best[t.first]=min1(best[t.first],t.second);
}
hasBeenCentr[cen]=1;
}
int best_path(int N, int K, int H[][2], int L[])
{
k=K;
for(int i=0;i<N-1;i++)
{
edg[H[i][0]].push_back({H[i][1],L[i]});
edg[H[i][1]].push_back({H[i][0],L[i]});
}
centrDec(0);
if(ans==inf)return -1;
return ans;
}
