#include"race.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
int k,inf=2e9,ans=inf,t,res[1000005],mt[1000005],a[200005];
bool vis[200005];
vector<pair<int,int>>g[200005];
void app(int v,int p,int len,int depth){
if(k>len&&mt[k-len]==t)ans=min(ans,depth+res[k-len]);
else if(k==len)ans=min(ans,depth);
if(len>k)return;
for(auto to:g[v])
if(to.fr!=p&&!vis[to.fr])app(to.fr,v,len+to.sc,depth+1);
}
void update(int v,int p,int len,int depth){
if(k>len&&mt[len]!=t){
mt[len]=t;
res[len]=depth;
}else if(k>len)res[len]=min(depth,res[len]);
else return;
for(auto to:g[v])
if(to.fr!=p&&!vis[to.fr])update(to.fr,v,len+to.sc,depth+1);
}
int dfs(int v,int p){
a[v]=1;
for(auto to:g[v])
if(to.fr!=p&&!vis[to.fr])
a[v]+=dfs(to.fr,v);
return a[v];
}
int centroid(int c){
dfs(c,c);
bool flag=true;
int v=c,p=v;
while(flag){
flag=false;
for(auto to:g[v]){
if(to.fr!=p&&!vis[to.fr]&&(a[to.fr]<<1)>=a[c]){
p=v;
v=to.fr;
flag=true;
break;
}
}
}
return v;
}
void go(int v){
v=centroid(v);
vis[v]=1;
t++;
for(auto to:g[v])
if(!vis[to.fr]){
app(to.fr,v,to.sc,1);
update(to.fr,v,to.sc,1);
}
for(auto to:g[v])
if(!vis[to.fr])go(to.fr);
}
int best_path(int N,int K,int H[][2],int L[]){
k=K;
for(int i=0;i+1<N;i++){
g[H[i][0]].push_back({H[i][1],L[i]});
g[H[i][1]].push_back({H[i][0],L[i]});
}
go(0);
if(ans==inf)return -1;
return ans;
}
