#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> dis;
vector<int> sz;
vector<int> par;
vector<vector<pair<int,int>>> adj;
vector<bool> vis;
int ans=1e6;
int need;
void szdfs(int node, int parent){
par[node]=parent;
sz[node]=1;
for(int i=0; i<(int) adj[node].size(); ++i){
int x= adj[node][i].first;
if(vis[x] || node==parent) continue;
szdfs(x, node);
sz[node]+=sz[x];
}
}
int Centroid (int node, int siz){
for(int i=0; i<(int) adj[node].size(); ++i){
int x= adj[node][i].first;
if(par[x]!=node || vis[x]) continue;
if(sz[x] > siz/2){
return Centroid ( x, siz);
}
}
return node;
}
queue<pair<int,int>>q;
void distances (int node, int d, int c){
for(int i=0; i<(int) adj[node].size(); ++i){
int x=adj[node][i].first;
int y=adj[node][i].second;
d+=y;
if(d<=need){
if(dis[need-d]!=0){
ans=min(ans, dis[need-d]+c);
}
}
q.push({d, c});
distances(x, d, c+1);
}
}
void Centroid_desc (int node){
szdfs(node, -1);
int root= Centroid ( node, sz[node]);
for(int i=0; i<(int) adj[root].size(); ++i){
distances(adj[root][i].first, adj[root][i].second, 1);
while(!q.empty()){
dis[q.front().first]=min(dis[q.front().first], q.front().second);
q.pop();
}
}
if(dis[need]!=0){
ans=min(ans, dis[need]);
}
vis[root]=1;
for(int i=0; i<(int) adj[root].size(); ++i){
Centroid_desc(adj[root][i].first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
dis.resize(K+5);
sz.resize(N);
par.resize(N);
adj.resize(N);
vis.resize(N);
for(int i=0; i<N-1; ++i){
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0],L[i]});
}
need=K;
Centroid_desc(0);
return ans;
}
