#include <bits/stdc++.h>
#define ll long long int
#define mp make_pair
#include "race.h"
using namespace std;
int ans;
const ll lim=200005;
const ll lim2=2000000;
int vis[lim],sz[lim],ok[lim2],add[lim2];
vector<pair<int,int>> g[lim];
int kk;
int timer=1;
void dfs_sz(int node,int p){
sz[node]=1;
for(auto x:g[node]){
if(x.first==p)continue;
if(vis[x.first])continue;
dfs_sz(x.first,node);
sz[node]+=sz[x.first];
}
}
int centroid(int &cnt,int node,int p){
for(auto x:g[node]){
if(x.first==p)continue;
if(vis[x.first])continue;
if(sz[x.first]>(cnt/2)){
return centroid(cnt,x.first,node);
}
}
return node;
}
void solve(int node,int p,ll dis,int cnt,vector<pair<ll,ll>> &info){
if(dis<=kk && ok[kk-dis]==timer){ //if a valid path exists
ans=min(ans,cnt+add[kk-dis]);
}
if(dis<=kk){
info.push_back({dis,cnt}); //record information
for(auto x:g[node]){
if(x.first==p)continue;
if(!vis[x.first]){
solve(x.first,node,dis+x.second,cnt+1,info);
}
}
}
}
void create(int root,int p){
dfs_sz(root,p); //-> find size
int c=centroid(sz[root],root,p); //find new centroid
vis[c]=true; //visited
++timer;
ok[0]=timer;
add[0]=0; //updating info
for(auto x:g[c]){ //for every subtree in centroid find paths ..will help in finding if there exists some path that posses through centrod
if(vis[x.first])continue;
if(x.first==p)continue;
vector<pair<ll,ll>> v;
solve(x.first,c,x.second,1,v);
for(auto y:v){ //updating info
if(ok[y.first]!=timer){
ok[y.first]=timer;
add[y.first]=y.second;
}else{
if(add[y.first]>y.second){
ok[y.first]=timer;
add[y.first]=y.second;
}
}
}
}
for(auto x:g[c]){
if(x.first==p)continue; //centroid decom
if(!vis[x.first])create(x.first,c);
}
}
int best_path(int n, int k, int h[][2], int l[])
{
ans=2*n;
for(int i=1;i<=n;i++){
g[i].clear();
vis[i]=false;
sz[i]=0;
ok[i]=0;
add[i]=0;
}
ok[0]=0;
add[0]=0;
for(int i=n;i<lim2;i++){
ok[i]=0;
add[i]=0;
}
timer=1;
kk=k;
for(int i=0;i<n-1;i++){
g[h[i][0]].push_back({h[i][1],l[i]});
g[h[i][1]].push_back({h[i][0],l[i]});
}
create(1,-1);
if(ans==(2*n))ans=-1;
return ans;
}
