#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll inf = 1e9, infl = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 1e6 + 5;
ll n, m, k = 0;
#include "race.h"
mt19937 rng(time(0));
ll sz[maxn], vis[maxn], rn = 0;
array<ll, 2> a[maxn];
vector<array<ll, 2>> g[maxn];
ll dfs(ll u, ll p = -1){
sz[u] = 1;
for(auto [v, w] : g[u]){
if(v == p or vis[v]) continue;
sz[u] += dfs(v, u);
}
return sz[u];
}
ll fc(ll u, ll p, ll x){
for(auto [v, w] : g[u]){
if(v == p or vis[v]) continue;
if(sz[v] >= sz[x] / 2) return fc(v, u, x);
}
return u;
}
void calc(ll u, ll p, ll cm, ll lv, set<array<ll, 2>> &ss){
if(cm > m) return;
ss.insert({cm, lv});
for(auto [v, w] : g[u]){
if(v == p or vis[v]) continue;
calc(v, u, cm + w, lv + 1, ss);
}
}
set<array<ll, 2>> ss;
void centree(ll u){
dfs(u);
ll cent = fc(u, -1, u);
vis[cent] = 1;
rn ++;
for(auto [v, w] : g[cent]){
ss.clear();
calc(v, cent, w, 1, ss);
for(auto [x, y] : ss){
if(a[m - x][1] != rn) a[m - x] = {infl, rn};
k = min(k, a[m - x][0] + y);
}
for(auto [x, y] : ss){
if(a[x][1] != rn) a[x] = {infl, rn};
a[x][0] = min(a[x][0], y);
}
}
for(auto [v, w] : g[cent]) if(!vis[v]) centree(v);
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, m = K;
for(ll i = 1; i <= n - 1; i ++){
g[H[i - 1][0] + 1].push_back({H[i - 1][1] + 1, L[i - 1]});
g[H[i - 1][1] + 1].push_back({H[i - 1][0] + 1, L[i - 1]});
}
k = infl;
centree(1);
if(k == infl) k = -1;
return k;
}
// void _() {
// }
// signed main() {
// cin.tie(0)->sync_with_stdio(0);
// ll t = 1;
// // cin >> t;
// while(t --) _();
// }
