#include "race.h"
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const char nl = '\n', sp = ' ';
const int inf = 1e9;
struct centroid_decomposition {
int n, w;
int ans = inf;
vector<vector<pair<int, int> > > g;
vector<int> sz;
vector<bool> is_removed;
map<ll, int> mp;
centroid_decomposition(int n) : n(n) {
g.assign(n, {});
sz.assign(n, 0);
is_removed.assign(n, false);
}
void add_edge(int u, int v, int c) {
g[u].emplace_back(v, c);
g[v].emplace_back(u, c);
}
int get_size(int u, int p) {
sz[u] = 1;
for (auto &[v, _]: g[u]) {
if (v == p || is_removed[v]) continue;
sz[u] += get_size(v, u);
}
return sz[u];
}
int get_cent(int u, int p, int m) {
for (auto &[v, _]: g[u]) {
if (v == p || is_removed[v]) continue;
if (sz[v] * 2 > m) return get_cent(v, u, m);
}
return u;
}
void add(int u, int p, int depth, ll weight) {
if (mp.contains(weight)) {
mp[weight] = min(mp[weight], depth);
} else {
mp[weight] = depth;
}
for (auto &[v, c]: g[u]) {
if (v == p || is_removed[v]) continue;
add(v, u, depth + 1, weight + c);
}
}
void get_ans(int u, int p, int depth, ll weight) {
if (mp.contains(w - weight)) ans = min(ans, depth + mp[w - weight]);
for (auto &[v, c]: g[u]) {
if (v == p || is_removed[v]) continue;
get_ans(v, u, depth + 1, weight + c);
}
}
void decompose(int node = 0) {
int m = get_size(node, -1);
int centroid = get_cent(node, -1, m);
mp[0] = 0;
for (auto &[v, c]: g[centroid]) {
if (is_removed[v]) continue;
get_ans(v, centroid, 1, c);
add(v, centroid, 1, c);
}
mp.clear();
is_removed[centroid] = true;
for (auto &[v, _]: g[centroid]) {
if (is_removed[v]) continue;
decompose(v);
}
}
};
int best_path(int N, int K, int H[][2], int L[]) {
centroid_decomposition cd(N);
cd.w = K;
for (int i = 0; i < N - 1; i++) {
cd.add_edge(H[i][0], H[i][1], L[i]);
}
cd.decompose();
return (cd.ans == inf ? -1 : cd.ans);
}
// void solve() {
// int n;
// cin >> n;
// centroid_decomposition cd(n);
// cin >> cd.w;
// for (int i = 1; i < n; i++) {
// int u, v, c;
// cin >> u >> v >> c;
// cd.add_edge(u, v, c);
// }
// cd.decompose();
// cout << (cd.ans == inf ? -1 : cd.ans) << nl;
// }
// signed main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout.tie(nullptr);
//
// #ifndef ONLINE_JUDGE
// freopen("../in.txt", "r", stdin);
// freopen("../out.txt", "w", stdout);
// #endif
//
// int t = 1;
// // cin >> t;
// while (t--) {
// solve();
// }
// }
