#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
const int maxn=1e6+5;
int ans,k;
int cnt[maxn];
struct Centroid {
int N;
vector<vector<pair<int,int>>>E;
vector<bool>done;
vector<int>sub,pc,lev;
vector<vector<int>>dis;
void add_edge(int x,int y,int w){
E[x].push_back({y,w});
E[y].push_back({x,w});
}
void init(int _N){
N = _N;
E.resize(N);
done.resize(N);
sub.resize(N),pc.resize(N),lev.resize(N);
dis.resize(32-__builtin_clz(N));
for(int i = 0;i < (int)dis.size();i++) dis[i].resize(N);
}
void dfs(int nd,int pr){
for(auto i : E[nd]){
sub[i.first] = 1;
if(i.first != pr and !done[i.first]) dfs(i.first,nd), sub[nd] += sub[i.first];
}
}
int centroid(int nd){
dfs(nd,-1);
int sz = sub[nd];
while(1){
pair<int,int>mx = {0,0};
for(auto i : E[nd]) if(!done[i.first] and sub[i.first] < sub[nd])
if(sub[i.first] > mx.first) mx = {sub[i.first],i.first};
if(mx.first*2 <= sz) return nd;
nd = mx.second;
}
}
void calc_dis(int nd,int pr,int lvl,int ds){
dis[lvl][nd] = dis[lvl][pr] + 1;
if(ds <= k) ans = min(ans,cnt[k-ds]+dis[lvl][nd]);
for(auto i : E[nd]) if(i.first != pr and !done[i.first]) calc_dis(i.first,nd,lvl,ds+i.second);
}
void put(int nd,int pr,int lvl,int ds){
cnt[ds] = min(cnt[ds],dis[lvl][nd]);
for(auto i : E[nd]) if(i.first != pr and !done[i.first]) put(i.first,nd,lvl,ds+i.second);
}
void calc(int PC,int _nd){
int nd = centroid(_nd); done[nd] = 1,pc[nd] = PC;
sub[nd] = sub[_nd]; lev[nd] = (PC == -1 ? 0 : lev[PC] + 1);
dis[lev[nd]][nd] = 0;
for(int i = 0;i < maxn;i++) cnt[i] = 1e9;
cnt[0] = 0;
for(auto i : E[nd]) if(!done[i.first]) calc_dis(i.first,nd,lev[nd],i.second);
for(auto i : E[nd]) if(!done[i.first]) calc(nd,i.first);
}
};
int best_path(int N, int K, int H[][2], int L[]){
k = K;
Centroid CD;
CD.init(N);
for(int i = 0;i < N-1;i++) CD.add_edge(H[i][0],H[i][1],L[i]);
CD.calc(-1,0);
return ans;
}
// int main(){
// ios::sync_with_stdio(false);
// cin.tie(0);
// }
