#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int N = 200005;
const int L = 20;
const int K = 1000005;
vector<pair<int, int>> g[N];
int dep[N];
int tin[N], tout[N], par[L][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;
int dfs_t = 0;
void pre_dfs(int u, int p, int d, long long w) {
dep[u] = d;
wt[u] = w;
tin[u] = ++dfs_t;
par[0][u] = p;
for (auto &e : g[u]) {
int v, l;
tie(v, l) = e;
if (v != p) {
pre_dfs(v, u, d + 1, w + l);
}
}
tout[u] = dfs_t;
}
bool is_ancs(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v) {
if (is_ancs(u, v)) return u;
if (is_ancs(v, u)) return v;
for (int j = L - 1; j >= 0; j--) {
if (!is_ancs(par[j][v], u)) {
v = par[j][v];
}
}
return par[0][v];
}
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]) {
long long real_dist = wt[u] + wt[x] - 2 * wt[lca(u, x)];
int edges = dep[u] + dep[x] - 2 * dep[lca(u, x)];
if (real_dist <= real_k) {
ans = min(ans, edges + mn[real_k - real_dist]);
}
}
for (auto &x : child[v]) {
long long real_dist = wt[u] + wt[x] - 2 * wt[lca(u, x)];
int edges = dep[u] + dep[x] - 2 * dep[lca(u, x)];
if (real_dist <= real_k) {
aff.emplace_back(real_dist);
mn[real_dist] = min(mn[real_dist], edges);
}
}
}
}
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(0, 0, 0, 0);
for (int j = 1; j < L; j++) {
for (int i = 0; i < n; i++) {
par[j][i] = par[j - 1][par[j - 1][i]];
}
}
dfs(0, 0);
int root = centroid(0, 0, n);
decompose(0, -1);
cd_dfs(root, root);
int ans = 0x3f3f3f3f;
for (int i = 0; i < n; i++) {
ans = min(ans, query(i));
}
return (ans == 0x3f3f3f3f ? -1 : ans);
}
