#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define emb emplace_back
const int maxn = 2e5 + 5;
const int maxx = 1e6 + 5;
const int inf = 2e9;
vector<pii> adj[maxn];
int sz[maxn];
bool del[maxn];
vector<pii> dist;
int kk, ssz;
int prv[maxx];
int mn = inf;
void dfs1(int u, int pa){
sz[u] = 1;
for(auto [w, v] : adj[u]){
if(v == pa || del[v]) continue;
dfs1(v, u);
sz[u] += sz[v];
}
}
void dfs2(int u, int pa, int cnt, int d){
if(d > kk) return;
dist.emb(d, cnt);
for(auto [w, v] : adj[u]){
if(v == pa || del[v]) continue;
dfs2(v, u, cnt + 1, d + w);
}
}
int cen(int u, int pa){
for(auto [w, v] : adj[u]){
if(v == pa || del[v]) continue;
if(sz[v] * 2 > ssz){
return cen(v, u);
}
}
return u;
}
void solve(int u){
dfs1(u, -1);
ssz = sz[u];
int c = cen(u, -1);
vector<int> used;
for(auto [w, v] : adj[c]){
if(del[v]) continue;
dist.clear();
dfs2(v, c, 1, w);
for(auto [d, cnt] : dist){
if(prv[kk - d] != inf) mn = min(mn, prv[kk - d] + cnt);
}
for(auto [d, cnt] : dist){
prv[d] = min(prv[d], cnt);
used.emb(d);
}
}
for(auto e : used) prv[e] = inf;
used.clear();
del[c] = 1;
for(auto [w, v] : adj[c]){
if(!del[v]) solve(v);
}
}
int best_path(int n, int k, int h[][2], int l[]){
kk = k;
for(int i=0;i<n-1;++i){
int u = h[i][0], v = h[i][1], w = l[i];
adj[u].emb(w, v);
adj[v].emb(w, u);
}
fill(prv+1, prv + maxx, inf);
solve(0);
return (mn == inf ? -1 : mn);
}
