#include <bits/stdc++.h>
#include "race.h"
using namespace std;
constexpr int N = 2e5 + 5;
constexpr int inf = 1e9;
vector<pair<int, int>> g[N];
int sz[N];
bool deleted[N];
map<int, int> mn;
int k, ans = inf, mx = 0;
void dfs_size(int u, int p) {
sz[u] = 1;
for (auto [v, w] : g[u]) {
if (v == p || deleted[v]) continue;
dfs_size(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int p, int n) {
for (auto [v, w] : g[u]) {
if (v == p || deleted[v]) continue;
if (sz[v] * 2 > n) {
return find_centroid(v, u, n);
}
}
return u;
}
void dfs(int u, int p, int d, int sum, bool upd) {
if (sum > k) return;
mx = max(mx, sum);
if (upd) {
if (mn.count(sum)) {
mn[sum] = min(mn[sum], d);
} else {
mn[sum] = d;
}
} else {
if (mn.count(k - sum)) {
ans = min(ans, d + mn[k - sum]);
}
}
for (auto [v, w] : g[u]) {
if (v == p || deleted[v]) continue;
dfs(v, u, d + 1, sum + w, upd);
}
}
void go(int u) {
dfs_size(u, -1);
int r = find_centroid(u, -1, sz[u]);
mx = 0;
mn[0] = 0;
for (auto [v, w] : g[r]) {
if (!deleted[v]) {
dfs(v, r, 1, w, 0);
dfs(v, r, 1, w, 1);
}
}
mn.clear();
deleted[r] = 1;
for (auto [v, w] : g[r]) {
if (!deleted[v]) {
go(v);
}
}
}
int best_path(int n, int _k, int h[][2], int l[]) {
k = _k;
for (int i = 0; i < n - 1; i++) {
int u = h[i][0], v = h[i][1], w = l[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
go(0);
return (ans == inf ? -1 : ans);
}
