#include <bits/stdc++.h>
#include "race.h"
#define pb emplace_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
const int MAXN = 200000;
vector <vector<pii>> path;
vector <bool> vis;
vector <int> sze;
vector <pii> d;
int n;
int ans, k;
void init(int N) {
path.clear();
path.resize(N);
vis.clear();
vis.resize(N);
sze.clear();
sze.resize(N);
d.clear();
ans = MAXN;
}
int dfs_sze(int now, int par) {
sze[now] = 1;
for (pii e : path[now]) {
if (vis[e.ff] || e.ff == par) continue;
sze[now] += dfs_sze(e.ff, now);
}
return sze[now];
}
int fnd_cen(int now, int par) {
for (pii e : path[now]) {
if (vis[e.ff] || e.ff == par) continue;
if (sze[e.ff] * 2 > n)
return fnd_cen(e.ff, now);
}
return now;
}
void dfs_dis(int now, int par, int sum, int dth) {
if (sum > k) return;
d.pb(sum, dth);
for (pii e : path[now]) {
if (vis[e.ff] || e.ff == par) continue;
dfs_dis(e.ff, now, sum+e.ss, dth+1);
}
}
void solve(int now, int par) {
n = dfs_sze(now, -1);
int r = fnd_cen(now, -1);
vis[r] = 1;
unordered_map <int,int> dis;
for (pii e : path[r]) {
if (vis[e.ff] || e.ff == par) continue;
dfs_dis(e.ff, -1, e.ss, 1);
for (pii it : d) {
if (dis.count(k-it.ff)) {
ans = min(ans, dis[k-it.ff] + it.ss);
} else if (it.ff == k) {
ans = min(ans, it.ss);
}
}
for (pii it : d) {
if (!dis.count(it.ff)) {
dis[it.ff] = it.ss;
} else {
dis[it.ff] = min(dis[it.ff], it.ss);
}
}
d.clear();
}
dis.clear();
for (pii e : path[r]) {
if (vis[e.ff] || e.ff == par) continue;
solve(e.ff, now);
}
return;
}
int best_path(int N, int K, int H[][2], int L[]) {
init(N);
k = K;
for (int i = 0; i < N-1; i++) {
path[H[i][0]].pb(H[i][1], L[i]);
path[H[i][1]].pb(H[i][0], L[i]);
}
solve(0, -1);
return ans == MAXN ? -1 : ans;
}
