#include <bits/stdc++.h>
#include "race.h"
using namespace std;
struct edge{
int v,cost;
};
const int INF=1e9;
int N,K,Ans,t;
int Size[200000],Min_Depth[1000001],Min_Depth_Visited[1000001];
bool Visited[200000];
vector<edge> Edge[200000];
int get_size(int v,int par=-1){
int &ret=Size[v]=1;
for (edge i:Edge[v]){
if (Visited[i.v]||i.v==par)
continue;
ret+=get_size(i.v,v);
}
return ret;
}
int get_cent(int v,int sz,int par=-1){
for (edge i:Edge[v]){
if (Visited[i.v]||i.v==par)
continue;
if (Size[i.v]*2>sz)
return get_cent(i.v,sz,v);
}
return v;
}
int dfs1(int v,int dist,int par,int depth=1){
if (dist>K)
return INF;
int ret=INF;
if (Min_Depth_Visited[K-dist]==t)
ret=depth+Min_Depth[K-dist];
for (edge i:Edge[v]){
if (Visited[i.v]||i.v==par)
continue;
ret=min(ret,dfs1(i.v,dist+i.cost,v,depth+1));
}
return ret;
}
void dfs2(int v,int dist,int par,int depth=1){
if (dist>K)
return;
if (Min_Depth_Visited[dist]!=t){
Min_Depth_Visited[dist]=t;
Min_Depth[dist]=depth;
}
else
Min_Depth[dist]=min(Min_Depth[dist],depth);
for (edge i:Edge[v]){
if (Visited[i.v]||i.v==par)
continue;
dfs2(i.v,dist+i.cost,v,depth+1);
}
}
int solve(int v){
t++;
Min_Depth_Visited[0]=t;
int ret=INF;
int cent=get_cent(v,get_size(v));
Visited[cent]=true;
for (edge i:Edge[cent]){
if (Visited[i.v])
continue;
ret=min(ret,dfs1(i.v,i.cost,cent));
dfs2(i.v,i.cost,cent);
}
for (edge i:Edge[cent]){
if (Visited[i.v])
continue;
ret=min(ret,solve(i.v));
}
return ret;
}
int best_path(int n,int k,int h[][2],int l[]){
N=n;
K=k;
for (int i=0; i<N-1; i++){
Edge[h[i][0]].push_back({h[i][1],l[i]});
Edge[h[i][1]].push_back({h[i][0],l[i]});
}
Ans=solve(0);
if (Ans==INF)
Ans=-1;
return Ans;
}
