#include "bits/stdc++.h"
#include "race.h"
// #include "grader.cpp"
using namespace std;
#define ll long long
vector <vector <pair <ll, ll>>> v;
vector <ll> dep, depth, s;
ll ans, KKK;
vector <map <ll, ll>> mp;
void dfs(int x, int y) {
s[x] = 1;
for(auto [i, j] : v[x]) {
if(i == y) continue;
dep[i] = dep[x] + j;
depth[i] = depth[x] + 1;
dfs(i, x);
s[x] += s[i];
}
}
void f(int x, int y) {
int mx = -1, hv = -1;
for(auto [i, j] : v[x]) {
if(i == y) continue;
f(i, x);
if(s[i] > mx) {
hv = i;
mx = s[i];
}
}
if(~hv) swap(mp[x], mp[hv]);
for(auto [i, j] : v[x]) {
if(i == hv or i == y) continue;
for(auto [k, nm] : mp[i]) {
if(mp[x].find(KKK - k + dep[x] * 2) == mp[x].end()) continue;
ans = min(ans, mp[x][KKK - k + dep[x] * 2] + nm - 2 * depth[x]);
}
for(auto [k, nm] : mp[i]) {
if(mp[x].find(k) == mp[x].end()) mp[x][k] = nm;
else mp[x][k] = min(nm, mp[x][k]);
}
}
if(mp[x].find(dep[x] + KKK) != mp[x].end()) ans = min(ans, mp[x][dep[x] + KKK] - depth[x]);
mp[x][dep[x]] = depth[x];
}
int best_path(int n, int KK, int h[][2], int l[]) {
KKK = KK;
mp.clear();
v.clear();
dep.clear();
depth.clear();
s.clear();
v.resize(n+1);
mp.resize(n+1);
dep.resize(n+1);
depth.resize(n+1);
s.resize(n+1);
dep[0] = 0;
depth[0] = 1;
for(int i = 0; i < n-1; i++) {
v[h[i][0]].push_back({h[i][1], l[i]});
v[h[i][1]].push_back({h[i][0], l[i]});
}
ans = 1e9;
dfs(0, -1);
f(0, -1);
assert(ans > 0);
return (ans == 1e9 ? -1 : ans);
}
