#include"race.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=2e5+5;
vector<ii> ds[MAXN];
bool ck[MAXN];
int sub[MAXN],D[MAXN*5],ans=1e9,k;
vector<int> vv;
vector<ii> vi;
void dfs(int i,int pre)
{
sub[i]=1;
for(auto v:ds[i]) if(v.fi!=pre&&!ck[v.fi])
{
dfs(v.fi,i);
sub[i]+=sub[v.fi];
}
}
int centroid(int i,int pre,int c)
{
for(auto v:ds[i]) if(v.fi!=pre&&!ck[v.fi]&&sub[v.fi]*2>c) return centroid(v.fi,i,c);
return i;
}
void solve(int i,int pre,int d,int e)
{
if(d>k) return ;
if(D[k-d]!=1e9) ans=min(ans,e+D[k-d]);
vi.push_back({d,e});
for(auto v:ds[i]) if(v.fi!=pre&&!ck[v.fi]) solve(v.fi,i,d+v.se,e+1);
}
void decomp(int i)
{
dfs(i,i);
int pos=centroid(i,i,sub[i]);
ck[pos]=true,D[0]=0;
for(auto v:ds[pos]) if(!ck[v.fi])
{
solve(v.fi,pos,v.se,1);
for(auto v:vi) vv.push_back(v.fi),D[v.fi]=min(D[v.fi],v.se);
vi.clear();
}
for(auto v:vv) D[v]=1e9;
vv.clear();
for(auto v:ds[pos]) if(!ck[v.fi]) decomp(v.fi);
}
int best_path(int N,int K,int H[][2],int L[])
{
k=K;
for(int i=0;i<=1e6;i++) D[i]=1e9;
for(int i=0;i<N-1;i++)
{
ds[H[i][0]].push_back({H[i][1],L[i]});
ds[H[i][1]].push_back({H[i][0],L[i]});
}
decomp(1);
if(ans==1e9) return -1;
return ans;
}
