#include <bits/stdc++.h>
#include <climits>
#include <cstring>
#include <vector>
using namespace std;
#define ll long long
using vll = vector<ll>;
using vvll = vector<vector<ll> >;
using mpll = map<pair<ll, ll>, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pi = pair<int, int>;
// we need to the shortest path with weights that sum to k
vector<vector<tuple<int,int>>> v;
vll height, sum; // of each node, from root, 0 at root
vector<map<ll, ll>> info; // info[node] is a map of sum: height of all nodes in subtree of node (incl)
ll ans;
int k;
void precomp(int c, int p=-1, int cs=0, int ch=0) {
height[c] = ch;
sum[c] = cs;
info[c][cs] = ch;
for (auto [vv, w]: v[c]) {
if (vv != p) precomp(vv, c, cs+w, ch+1);
}
}
void merge(int c, int p=-1) {
ll target = k + 2 * sum[c];
for (auto [vv, w]: v[c]) {
if (vv == p) continue;
merge(vv, c);
if (info[vv].size() > info[c].size()) swap(info[vv], info[c]);
for (auto [s, h]: info[vv]) {
if (info[c].find(target - s) != info[c].end()) {
ans = min(ans, info[c][target - s] + h - 2 * sum[c]);
}
}
for (auto [s, h]: info[vv]) {
if (info[c].find(s) != info[c].end()) {
info[c][s] = min(info[c][s], h);
} else {
info[c][s] = h;
}
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
height.clear(); sum.clear(); v.clear(); info.clear();
height.resize(N+1);
sum.resize(N+1);
v.resize(N+1);
info.resize(N+1);
k = K;
ans = INT_MAX;
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]});
}
precomp(0);
merge(0);
return ans == INT_MAX ? -1 : ans;
}
