#include "race.h"
#include <iostream>
using namespace std;
long long int ans=99999999999,a[1000005],t[1000005][2],p,num,f[1000005],tag[1000005],son[1000005],n,k,map[1000005][3],road[1000005];
int build(int x,int fa)
{
son[x]=1;
f[x]=fa;
long long int g=road[x];
while(g!=-1)
{
long long int now=map[g][0];
if(now!=fa && tag[now]==0)
{
build(now,x);
son[x]+=son[now];
}
g=map[g][1];
}
}
int find(int x,int fa,long long int sum)
{
long long int g=road[x];
long long int can=1;
if(sum>num/2)can=0;
while(g!=-1)
{
long long int now=map[g][0];
if(now!=fa && tag[now]==0)
{
long long int tmp=find(now,x,sum+son[x]-son[now]);
if(tmp!=-1)return tmp;
if(son[now]>num/2)can=0;
}
g=map[g][1];
}
if(can==0)return -1;
return x;
}
int dfs(int x,long long int len,int fa,int cnt)
{
if(len<=k)
{
p++;
t[p][0]=len;
t[p][1]=cnt;
}
long long int g=road[x];
while(g!=-1)
{
long long int now=map[g][0];
if(now!=fa && tag[now]==0)
{
dfs(now,len+map[g][2],x,cnt+1);
}
g=map[g][1];
}
}
int solve(int x)
{
build(x,-1);
num=son[x];
long long int st=find(x,-1,0);
long long int g=road[st],pp=1;
//cout<<"solve"<<st<<endl;
while(g!=-1)
{
long long int now=map[g][0];
// cout<<now<<endl;
if(tag[now]==0)
{
dfs(now,map[g][2],st,1);
for(int i=pp;i<=p;i++)
{
ans=min(ans,a[k-t[i][0]]+t[i][1]);
//cout<<t[i][0]<<" "<<t[i][1]<<" ";
}
//cout<<endl;
for(int i=pp;i<=p;i++)
{
a[t[i][0]]=min(a[t[i][0]],t[i][1]);
}
ans=min(ans,a[k]);
pp=p+1;
}
g=map[g][1];
}
for(int i=1;i<=p;i++)a[t[i][0]]=9999999999999999;
g=road[st];
tag[st]=1;
p=0;
while(g!=-1)
{
long long int now=map[g][0];
if(tag[now]==0)
{
solve(now);
}
g=map[g][1];
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;
k=K;
for(int i=1;i<=k;i++)a[i]=9999999999999999;
for(int i=0;i<n;i++)road[i]=-1;
for(int i=0;i<n-1;i++)
{
map[i*2][0]=H[i][0];
map[i*2][1]=road[H[i][1]];
map[i*2][2]=L[i];
road[H[i][1]]=i*2;
map[i*2+1][0]=H[i][1];
map[i*2+1][1]=road[H[i][0]];
map[i*2+1][2]=L[i];
road[H[i][0]]=i*2+1;
}
solve(0);
if(ans==99999999999)return -1;
return ans;
}
