#include <bits/stdc++.h>
#define MAX 205000
bool existe[MAX];
typedef std::pair<int,int> pii;
std::vector<pii> con[MAX];
int dfs(int pos,int prev){
int size=1;
for(auto&y:con[pos]){
auto x = y.first;
if(x==prev||existe[x])continue;
size+=dfs(x,pos);
}
return size;
}
int centroide=0;
int find(int pos,int prev,int sz){
int size=1;
int max=0;
for(auto&y:con[pos]){
auto x = y.first;
if(x==prev||existe[x])continue;
int b = find(x,pos,sz);
max=std::max(max,b);
size+=b;
}
max=std::max(max,sz-size);
if(max<=sz/2)centroide=pos;
return size;
}
int Quer;
int best=1e9;
std::unordered_map<int,int> tabela;
void explorar(int pos,int prev,int dist1=0,int dist2=0){
if(dist1>Quer)return;
if(dist1==Quer){
best=std::min(best,dist2);
}
if(dist1<Quer){
int falta = Quer-dist1;
auto it = tabela.find(falta);
if(it!=tabela.end()){
best=std::min(best,it->second+dist2);
}
}
for(auto&x:con[pos]){
if(x.first==prev||existe[x.first])continue;
explorar(x.first,pos,dist1+x.second,dist2+1);
}
}
void computar(int pos,int prev,int dist1=0,int dist2=0){
if(dist1>Quer)return;
if(dist1<Quer){
auto it = tabela.find(dist1);
if(it==tabela.end()){
tabela[dist1]=dist2;
}else it->second=std::min(it->second,dist2);
}
for(auto&x:con[pos]){
if(x.first==prev||existe[x.first])continue;
computar(x.first,pos,dist1+x.second,dist2+1);
}
}
void Decompor(int x){
int tam = dfs(x,-1);
find(x,-1,tam);
int c = centroide;
existe[c]=true;
for(auto&x:con[c]){
if(existe[x.first])continue;
explorar(x.first,-1,x.second,1);
computar(x.first,-1,x.second,1);
}
tabela.clear();
for(auto&y:con[c]){
auto x = y.first;
if(existe[x])continue;
Decompor(x);
}
}
int best_path(int N, int K, int H[][2], int L[]){
for(int i=0;i!=N-1;++i){
int a = H[i][0],b=H[i][1],c=L[i];
con[a].push_back({b,c});
con[b].push_back({a,c});
}
Quer=K;
best=1e9;
Decompor(0);
return best;
}
