#include "race.h"
#include <stdio.h>
#include <vector>
using namespace std;
#define ll long int
#define pb push_back
#define mp make_pair
const int N=200050;
const int M=1000050;
const int inf=1e9;
int min(int a, int b){ return a>b?b:a;}
vector<pair<int,int> > E[N];
void AddEdge(int u, int v, int w){ E[u].pb(mp(v,w));E[v].pb(mp(u,w));}
int k;
int sz[N];
bool vis[N];
void DFS(int u, int p, int &n)
{
n++;sz[u]=1;
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].first;
if(v!=p && !vis[v]) DFS(v,u,n),sz[u]+=sz[v];
}
}
int Find(int u, int p, int n)
{
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].first;
if(v!=p && !vis[v] && sz[v]>n/2) return Find(v,u,n);
}
return u;
}
int Find(int u){ int n=0;DFS(u,u,n);return Find(u,u,n);}
vector<pair<int,int> > bck,lzy;
int Min[M],ans=inf;
void Solve(int u, int p, int d, int w)
{
if(w>k) return;
bck.pb(mp(w,d));
lzy.pb(mp(w,d));
ans=min(ans,Min[k-w]+d);
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].first;
int add=E[u][i].second;
if(v!=p && !vis[v]) Solve(v,u,d+1,w+add);
}
}
void Decompose(int u)
{
u=Find(u);vis[u]=1;
int i,j;
Min[0]=0;
lzy.pb(mp(0,0));
for(i=0;i<E[u].size();i++)
{
int v=E[u][i].first;
int w=E[u][i].second;
if(!vis[v])
{
Solve(v,u,1,w);
for(j=0;j<bck.size();j++) Min[bck[j].first]=min(Min[bck[j].first],bck[j].second);
bck.clear();
}
}
for(i=0;i<lzy.size();i++) Min[lzy[i].first]=inf;
lzy.clear();
for(i=0;i<E[u].size();i++)
{
int v=E[u][i].first;
if(!vis[v]) Decompose(v);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
int i;k=K;int n=N;
for(i=0;i<n-1;i++) AddEdge(H[i][0]+1,H[i][1]+1,L[i]);
for(i=0;i<=k;i++) Min[i]=inf;
Decompose(1);
if(ans==inf) return -1;
return ans;
}
