#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int nax=2e5+5;
const int vax=1e6+5;
typedef long long ll;
vector<array<int,3> > grafo[nax];
int ans=INT_MAX;
int N,K;
int ss,cc;
int m[vax];
void incl(int n, int a, int d, int v){
if(K<v)return;
if(a!=-1){
if(m[K-v]!=-1)ans=min(ans,m[K-v]+d);
if(m[v]==-1)m[v]=d;
else m[v]=min(m[v],d);
}else{
fill(m,m+vax,-1);
}
for(auto x:grafo[n]){
if(!x[2]||x[0]==a)continue;
incl(x[0],n,d+1,v+x[1]);
}
}
int findc(int n, int a, int& c, int num){
int s=0;
for(auto x:grafo[n]){
if(!x[2]||x[0]==a)continue;
s+=findc(x[0],n,c,num);
}
if(abs(s-num/2)<=1)c=n;
return s+1;
}
int findsize(int n, int a){
int s=0;
for(auto x:grafo[n]){
if(!x[2]||x[0]==a)continue;
s+=findsize(x[0],n);
}
return s+1;
}
void centroid(int n){
incl(n,-1,0,0);
for(int i=0;i<grafo[n].size();i++)grafo[n][i][2]=0;
for(auto x:grafo[n]){
ss=findsize(x[0],-1);
findc(x[0],-1,cc,ss);
centroid(cc);
}
}
int best_path(int N, int K, int H[][2], int L[]){
::N=N,::K=K;
for(int i=0;i<N-1;i++){
grafo[H[i][0]].push_back({H[i][1],L[i],1});
grafo[H[i][1]].push_back({H[i][0],L[i],1});
}
ss=findsize(0,-1);
findc(0,-1,cc,ss);
centroid(cc);
return ans;
}
