#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int N = 200005;
const int K = 1000005;
vector<pair<int, int>> g[N];
int dep[N];
long long wt[N];
vector<int> cd[N];
int fa[N], sz[N];
bool rmv[N];
vector<int> child[N];
int mn[K];
int real_k;
void pre_dfs(int u, int p, int d, long long w) {
dep[u] = d;
wt[u] = w;
for (auto &e : g[u]) {
int v, l;
tie(v, l) = e;
if (v != p) {
pre_dfs(v, u, d + 1, w + l);
}
}
}
void dfs(int u, int p) {
sz[u] = 1;
for (auto &e : g[u]) {
int v, w;
tie(v, w) = e;
if (!rmv[v] && v != p) {
dfs(v, u);
sz[u] += sz[v];
}
}
}
int centroid(int u, int p, int n) {
for (auto &e : g[u]) {
int v, w;
tie(v, w) = e;
if (v != p && !rmv[v]) {
if (sz[v] > n / 2) {
return centroid(v, u, n);
}
}
}
return u;
}
void decompose(int u, int p) {
dfs(u, p);
int n = sz[u];
int c = centroid(u, u, n);
if (p == -1) {
fa[c] = c;
} else {
fa[c] = p;
cd[c].emplace_back(p);
cd[p].emplace_back(c);
}
rmv[c] = true;
for (auto &e : g[c]) {
int v, w;
tie(v, w) = e;
if (!rmv[v]) {
decompose(v, c);
}
}
}
void cd_dfs(int u, int p) {
child[u].emplace_back(u);
for (auto &v : cd[u]) {
if (v != p) {
cd_dfs(v, u);
for (auto &x : child[v]) {
child[u].emplace_back(x);
}
}
}
}
int query(int u) {
int ans = 0x3f3f3f3f;
vector<int> aff;
mn[0] = 0;
aff.emplace_back(0);
for (auto &v : cd[u]) {
if (v != fa[u]) {
for (auto &x : child[v]) {
if (llabs(wt[u] - wt[x]) <= real_k) {
ans = min(ans, abs(dep[u] - dep[x]) + mn[real_k - llabs(wt[u] - wt[x])]);
}
}
for (auto &x : child[v]) {
if (llabs(wt[u] - wt[x]) <= real_k) {
aff.emplace_back(llabs(wt[u] - wt[x]));
mn[llabs(wt[u] - wt[x])] = min(mn[llabs(wt[u] - wt[x])], abs(dep[u] - dep[x]));
}
}
}
}
for (auto &x : aff) {
mn[x] = 0x3f3f3f3f;
}
return ans;
}
int best_path(int n, int k, int h[][2], int l[]) {
memset(mn, 0x3f, sizeof(mn));
real_k = k;
for (int i = 0; i < n - 1; i++) {
g[h[i][0]].emplace_back(h[i][1], l[i]);
g[h[i][1]].emplace_back(h[i][0], l[i]);
}
pre_dfs(1, 1, 0, 0);
int root = centroid(1, 1, n);
decompose(1, -1);
cd_dfs(root, root);
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n; i++) {
ans = min(ans, query(i));
}
return (ans == 0x3f3f3f3f ? -1 : ans);
}
