#include "race.h"
#include<bits/stdc++.h>
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"
using namespace std;
using pii = pair<int, int>;
const int N = (int)2e5 + 7; // make sure this is right
const int inf = (int)1e9;
const ll INF = (ll)3e18 + 7;
const ll MOD = (ll)1e9 + 7; // make sure this is right
pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n, k, d[N], ans = inf;
vector<pii> g[N];
map<ll, int> mn[N];
int comb(map<ll, int> &a, map<ll, int> &b, int q, ll w) {
int res = inf;
if(sz(a) < sz(b)) {
for(auto [x, y] : a) {
if(b.count(k + 2 * w - x)) {
res = min(res, y + b[k + 2 * w - x] - 2 * q);
}
}
for(auto [x, y] : a) {
if(!b.count(x)) {
b[x] = y;
} else b[x] = min(b[x], y);
}
a.swap(b);
b.clear();
} else {
for(auto [x, y] : b) {
if(a.count(k + 2 * w - x)) {
res = min(res, y + a[k + 2 * w - x] - 2 * q);
}
}
for(auto [x, y] : b) {
if(!a.count(x)) a[x] = y;
else a[x] = min(a[x], y);
}
}
return res;
}
void dfs(int v, int pr, ll len) {
for(auto [to, w] : g[v]) {
if(to == pr) continue;
d[to] = d[v] + 1;
dfs(to, v, len + w);
}
for(auto [to, w] : g[v]) {
ans = min(ans, comb(mn[v], mn[to], d[v], len));
}
mn[v][len] = d[v];
if(mn[v].count(len + k)) {
ans = min(ans, mn[v][len + k] - d[v]);
}
}
int best_path(int n_, int k_, int h_[][2], int l_[]) {
n = n_;
k = k_;
for(int i = 0; i < n - 1; ++i) {
h_[i][0]++;
h_[i][1]++;
g[h_[i][0]].pb({h_[i][1], l_[i]});
g[h_[i][1]].pb({h_[i][0], l_[i]});
}
dfs(1, 1, 0);
return (ans == inf ? -1 : ans);
}
