#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int N=1e6+10,INF=1e9;
int n,k;
int h[N],e[N],ne[N],w[N],idx;
int sz[N],mx[N],vis[N],sum,root;
pair<int,int> s[N];
int f[N];
int ans;
int tp;
int q[N];
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void getroot(int u,int fa)
{
sz[u]=1;
mx[u]=0;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa||vis[j]) continue;
getroot(j,u);
sz[u]+=sz[j];
mx[u]=max(mx[u],sz[j]);
}
mx[u]=max(mx[u],sum-sz[u]);
if(mx[root]>mx[u]) root=u;
}
void getdis(int u,int fa,int d,int p)
{
if(d>k) return;
s[++tp]=make_pair(d,p);
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa||vis[j]) continue;
getdis(j,u,d+w[i],p+1);
}
}
void solve(int u)
{
int cnt=0;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(vis[j]) continue;
tp=0;
getdis(j,u,w[i],1);
for(int i=1;i<=tp;i++) ans=min(ans,s[i].second+f[k-s[i].first]);
for(int i=1;i<=tp;i++) f[q[++cnt]=s[i].first]=min(f[s[i].first],s[i].second);
}
for(int i=1;i<=cnt;i++) f[q[i]]=INF;
}
void dfs(int u)
{
vis[u]=1;
f[0]=0;
solve(u);
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(vis[j]) continue;
root=0;
sum=sz[j];
getroot(j,u);
dfs(root);
}
}
int best_path(int N, int K, int tt[][2], int l[])
{
n=N,k=K;
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++)
{
++tt[i][0],++tt[i][1];
add(tt[i][0],tt[i][1],l[i]);
add(tt[i][1],tt[i][0],l[i]);
}
for(int i=0;i<=k;i++) f[i]=INF;
ans=mx[0]=INF;
root=0;
sum=n;
getroot(1,0);
dfs(root);
if(ans==INF) return -1;
return ans;
}
