#include "race.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll array<ll, 2>
#define ss second
#define ff first
using namespace std;
const ll N = 2e5 + 5;
const int inf = INT_MAX;
ll ans = inf;
vector<vector<pll>>g;
ll ch[N], sz[N]; map<ll, ll>dis;
ll dfs(ll u, ll p){
sz[u] = 1;
for(auto &[v, W] : g[u]){
if(v == p or ch[v]) continue;
sz[u] += dfs(v, u);
}
return sz[u];
}
ll get_cent(ll u, ll p, ll mx){
for(auto &[v, W] : g[u]){
if(v == p or ch[v]) continue;
if(sz[v] > mx / 2) return get_cent(v, u, mx);
}
return u;
}
void search(ll u, ll p, ll k, queue<pll> &nw, ll d = 0, ll W = 0){
if(dis.count(k - W)) ans = min(ans, dis[k - W] + d);
nw.push({d, W});
for(auto &[v, w] : g[u]){
if(v == p or ch[v]) continue;
search(v, u, k, nw, d + 1, W + w);
}
}
void get_ans(ll u, ll p, ll k){
ll cent = get_cent(u, p, dfs(u, p));
dis[0] = 0; queue<pll>nw;
for(auto &[v, w] : g[cent]){
if(ch[v]) continue;
search(v, cent, k, nw, 1, w);
while(!nw.empty()){
auto [d, W] = nw.front();
nw.pop();
auto it = dis.find(W);
if(it == dis.end()) dis[W] = d;
else dis[W] = min(it->ss, d);
}
}
ch[cent] = 1;
dis.clear();
for(auto &[v, W] : g[cent]){
if(ch[v]) continue;
get_ans(v, cent, k);
}
}
int best_path(int n, int k, int h[][2], int l[]){
g.assign(n, {});
for(ll i = 0; i < n - 1; i++){
auto [a, b] = h[i];
g[a].pb({b, l[i]}), g[b].pb({a, l[i]});
}
get_ans(0, -1, k); return (ans == inf ? -1 : ans);
}
