#include "race.h"
#include<bits/stdc++.h>
using namespace std;
int n,k,tam[200005],lv[200005],vis[200005],ans=1e9,val[1000005];
vector<pair<int,int> > adj[200005];
void tamanio_tree(int u,int p){
tam[u]=1;
for(auto [node,w]:adj[u]){
if(vis[node]==0&&node!=p){
tamanio_tree(node,u);
tam[u]+=tam[node];
}
}
}
int centroid_descomposition(int u,int p,int want){
for(auto [node,w]:adj[u]){
if(node!=p&&vis[node]==0){
if(tam[node]>want)return centroid_descomposition(node,u,want);
}
}
return u;
}
void dfs(int u,int p,int depth,int lv,int type){
if(depth>k)return;
if(type==1){
ans=min(ans,lv+val[k-depth]);
}else if(type==0){
val[depth]=min(val[depth],lv);
}else{
val[depth]=1e9,val[k-depth]=1e9;
}
for(auto [node,w]: adj[u]){
if(node!=p&&vis[node]==0) {
dfs(node,u,depth+w,lv+1,type);
}
}
}
void all_trees(int u){
tamanio_tree(u,u);
int c = centroid_descomposition(u,u,n/2);
vis[c] = 1;
for(auto [v,w] : adj[c]){
if(!vis[v]){
dfs(v,v,w,1,2);
}
}
val[0] = 0;
for(auto [v,w] : adj[c]){
if(!vis[v]){
dfs(v,v,w,1,1);
dfs(v,v,w,1,0);
}
}
for(auto [v,w] : adj[c]){
if(!vis[v]){
all_trees(v);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
for(int i=0;i<n-1;i++){
adj[H[i][0]+1].push_back({H[i][1]+1,L[i]});
adj[H[i][1]+1].push_back({H[i][0]+1,L[i]});
}
for(int i=1;i<=n;i++){
vis[i]=0;
}
for(int i=1;i<=1000000;i++){
val[i] = 1e9;
}
all_trees(1);
return (ans == 1e9) ? -1 : ans;
}
