#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct idg
{
int y,v;
};
int n,k;
int idx,ans,mx;
vector<idg> G;
vector<int> nxt,top,cen,sz,d;
void add_edge(int x,int y,int v)
{
idx++;
G[idx]={y,v};
nxt[idx]=top[x];
top[x]=idx;
}
int Size(int x,int tata)
{
sz[x]=1;
for(int i=top[x];i;i=nxt[i])
{
int y=G[i].y;
if(y==tata || cen[y])
continue;
sz[x]+=Size(y,x);
}
return sz[x];
}
int centroid(int x,int size,int tata)
{
for(int i=top[x];i;i=nxt[i])
{
int y=G[i].y;
if(y==tata || cen[y])
continue;
if(2*sz[y]>size)
return centroid(y,size,x);
}
return x;
}
void dfs(int x,int tata,int op,int edges,int dist)
{
if(dist>k)
return;
if(op==-1)
d[dist]=1e9;
if(op==0)
ans=min(ans,d[k-dist]+edges);
if(op==1)
d[dist]=min(d[dist],edges);
for(int i=top[x];i;i=nxt[i])
{
auto [y,v]=G[i];
if(y==tata || cen[y])
continue;
dfs(y,x,op,edges+1,dist+v);
}
}
void decompose(int x,int tata)
{
int c=centroid(x,Size(x,tata),tata);
d[0]=0;
for(int i=top[c];i;i=nxt[i])
{
auto [y,v]=G[i];
if(y==tata || cen[y])
continue;
dfs(y,c,1,1,v);
dfs(y,c,0,1,v);
}
dfs(c,0,-1,0,0);
cen[c]=1;
for(int i=top[c];i;i=nxt[i])
{
int y=G[i].y;
if(y==tata || cen[y])
continue;
decompose(y,c);
}
}
int best_path(int _n,int _k,int H[][2],int L[])
{
n=_n;
k=_k;
G=vector<idg>(2*n+5);
nxt=vector<int>(2*n+5);
top=cen=sz=vector<int>(n+5);
d=vector<int>(k+5,1e9);
ans=1e9;
for(int i=0;i<n-1;i++)
{
add_edge(H[i][0]+1,H[i][1]+1,L[i]);
add_edge(H[i][1]+1,H[i][0]+1,L[i]);
}
decompose(1,0);
if(ans>=1e9) ans=-1;
return ans;
}
