#include "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int ans=INT_MAX,sz[200001],k;
int dis[1000001];
int now[1000001];
vector<pii> adj[200001];
vector<int> temp,temp2;
bool mark[200001];
int find_sz(int x, int par) {
sz[x]=1;
for (auto s : adj[x]) {
if (s.first==par || mark[s.first]) continue;
sz[x]+=find_sz(s.first,x);
}
return sz[x];
}
int cen(int x, int par, int n) {
for (auto s : adj[x]) {
if (s.first!=par && !mark[s.first] && sz[s.first]>n/2) return cen(s.first,x,n);
}
return x;
}
void dfs(int x, int par, int d, int cnt) { // d=distance, consider node x
if (d<k) {
now[d]=min({now[d],cnt,dis[d]});
temp2.push_back(d);
temp.push_back(d);
if (dis[k-d]!=INT_MAX) ans=min(ans,cnt+dis[k-d]);
for (auto s : adj[x]) if (!mark[s.first] && s.first!=par) dfs(s.first,x,d+s.second,cnt+1);
} else if (d==k) ans=min(ans,cnt);
}
void sol(int x) {
int centroid=cen(x,x,find_sz(x,x));
mark[centroid]=true;
for (auto s : adj[centroid]) {
if (mark[s.first]) continue;
dfs(s.first,centroid,s.second,1);
for (auto s : temp2) dis[s]=now[s];
temp2.clear();
}
for (auto s : temp) dis[s]=INT_MAX,now[s]=INT_MAX;
temp.clear();
for (auto s : adj[centroid]) if (!mark[s.first]) sol(s.first);
}
int best_path(int n, int K, int H[][2], int L[]) {
k=K;
for (int i=1; i<=K; ++i) dis[i]=INT_MAX,now[i]=INT_MAX;
for (int i=0; i<n-1; ++i) {
adj[H[i][0]].push_back(pii(H[i][1],L[i]));
adj[H[i][1]].push_back(pii(H[i][0],L[i]));
}
sol(1);
if (ans==INT_MAX) return -1;
return ans;
}
