#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
const int MXN = 2e5+5;
const int MXK = 1e6+5;
const int inf = 1e9;
int n, k;
vector<pii> g[MXN];
int ans, mn[MXK];
int sz[MXN];
bool dead[MXN];
int get_sz(int v, int p=-1) {
sz[v] = 1;
for(auto [u, w] : g[v])
if(!dead[u] && u!=p)
sz[v] += get_sz(u, v);
return sz[v];
}
int centroid(int v, int N, int p=-1) {
for(auto [u, w] : g[v])
if(!dead[u] && u!=p && sz[u]+sz[u]>N)
return centroid(u, N, v);
return v;
}
void dfs1(int v, int h=0, ll W=0, int p=-1) {
if(W<=k) ans = min(ans, mn[k-W]+h);
for(auto [u, w] : g[v])
if(!dead[u] && u!=p)
dfs1(u, h+1, W+w, v);
}
void dfs2(int v, int h=0, ll W=0, int p=-1) {
if(W<=k) mn[W] = min(mn[W], h);
for(auto [u, w] : g[v])
if(!dead[u] && u!=p)
dfs2(u, h+1, W+w, v);
}
void dfs3(int v, ll W=0, int p=-1) {
if(W<=k) mn[W] = inf;
for(auto [u, w] : g[v])
if(!dead[u] && u!=p)
dfs3(u, W+w, v);
}
void solve(int v) {
dead[v = centroid(v, get_sz(v))] = 1;
mn[0] = 0;
for(auto [u, w] : g[v])
if(!dead[u]) {
dfs1(u, 1, w);
dfs2(u, 1, w);
}
mn[0] = inf;
for(auto [u, w] : g[v])
if(!dead[u])
dfs3(u, w);
for(auto [u, w] : g[v])
if(!dead[u])
solve(u);
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for(int i=0; i<n-1; i++ ){
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
ans = inf;
fill(mn, mn+k+1, inf);
solve(0);
return ans == inf ? -1 : ans;
}
