#include "race.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 2e5+5;
const int mxK = 2e6+5;
vector <pair <int, ll>> adj[mxN];
ll n, k, dis[mxN];
multiset <int> c[mxK];
int st[mxN], en[mxN], tt[mxN], it = 0, dep[mxN];
int mn = INT_MAX;
void dfs(int u, int p) {
st[u] = ++it;
tt[it] = u;
for (auto [v, w] : adj[u]) if (v != p) {
dep[v] = dep[u] + 1;
dis[v] = dis[u] + w;
dfs(v, u);
}
en[u] = it;
}
void sack(int u, int p, int keep) {
int mx = 0, idx = -1;
for (auto [v, w] : adj[u]) if (v != p) if (en[v] - st[v] + 1 > mx) idx = v, mx = en[v] - st[v] + 1;
for (auto [v, w] : adj[u]) if (v != p && v != idx) sack(v, u, 0);
if (idx > -1) sack(idx, u, 1);
c[dis[u]].emplace(dep[u]);
for (auto [v, w] : adj[u]) if (v != p && v != idx) {
for (int i = st[v]; i <= en[v]; i++) {
ll curr = dis[tt[i]] - dis[u];
if (curr > k) continue;
curr = k - curr + dis[u];
if (c[curr].empty()) continue;
mn = min(mn, dep[tt[i]] + *c[curr].begin() - 2 * (dep[u]));
}
for (int i = st[v]; i <= en[v]; i++) {
c[dis[tt[i]]].emplace(dep[tt[i]]);
}
}
if (c[dis[u] + k].size()) mn = min(mn, *c[dis[u] + k].begin() - dep[u]);
if (!keep) {
for (int i = st[u]; i <= en[u]; i++) {
c[dis[tt[i]]].erase(c[dis[tt[i]]].find(dep[tt[i]]));
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
for (int i = 0; i < n-1; i++) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
dfs(0, 0);
sack(0, 0, 1);
return (mn == INT_MAX ? -1 : mn);
}
