#include "race.h"
#include <bits/stdc++.h>
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)
#define all(v) v.begin(), v.end()
#define S second
#define F first
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);
#define pb push_back
using namespace std;
const int N = 5e5+5;
int a[N], b[N], c[N], n, m, l, ans = 2e9, k, sz[N], siz, d[N];
map<int, int>mp;
bool used[N];
vector <pair<int, int>> g[N];
void dfs(int v, int p = 0){
sz[v] = 1;
for(auto i : g[v]){
if(used[i.F] || p == i.F)continue;
dfs(i.F, v);
sz[v] += sz[i.F];
}
}
int find_c(int v, int p = 0){
for(auto i : g[v]){
if(used[i.F] || i.F == p)continue;
if(sz[i.F] * 2 > siz)return find_c(i.F, v);
}
return v;
}
void check(int v, int p, int cnt){
if(cnt > m)return;
if( mp[ m - cnt ] )ans = min(ans, mp[ m - cnt ] + d[v]);
if(cnt == m)ans = min(ans, d[v]);
for(auto i : g[v]){
if(i.F == p || used[i.F])continue;
d[i.F] = d[v] + 1;
check(i.F, v, cnt + i.S);
}
}
void go(int v, int p, int cnt){
if(cnt > m)return;
if(!mp[cnt] && cnt)mp[cnt] = d[v];
else mp[cnt] = min(mp[cnt], d[v]);
for(auto i : g[v]){
if(i.F == p || used[i.F])continue;
d[i.F] = d[v] + 1;
go(i.F, v, cnt + i.S);
}
}
void centroid(int v){
dfs(v);
siz = sz[v];
v = find_c(v);
d[v] = 0;
mp.clear();
mp[0] = 0;
used[v] = 1;
for(auto i : g[v]){
if(!used[i.F]){
d[i.F]= 1;
check(i.F, v, i.S);
d[i.F] = 1;
go(i.F, v, i.S);
}
}
for(auto i : g[v]){
if(!used[i.F])centroid(i.F);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
nikita
n = N, m = K;
FOR(i, 0, n-2, 1){
g[H[i][0]].pb({H[i][1], L[i]});
g[H[i][1]].pb({H[i][0], L[i]});
}
centroid(0);
if(ans==2e9)return -1;
return ans;
}
