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