#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
vector<pair<ll, pair<ll, ll>>> e;
vector<vector<ll>> A;
vector<bool> black;
vector<ll> sz;
ll n, k;
ll getsz(ll u, ll p){
sz[u]=1;
for (auto i:A[u]){
if (black[i]) continue;
ll v = e[i].ss.ff^e[i].ss.ss^u;
if (v==p) continue;
sz[u]+=getsz(v, u);
}
return sz[u];
}
void findcentroid(ll u, ll p, ll up, ll ¢r, ll wsz){
for (auto i:A[u]){
if (black[i]) continue;
ll v = e[i].ss.ff^e[i].ss.ss^u;
if (v==p) continue;
if (sz[v]>wsz/2) {findcentroid(v, u, up+1, centr, wsz); return;}
}
centr=u;
return;
}
void dfs(ll u, ll p, map<ll, ll> &usg, ll level, ll dep){
if (usg.count(level)) usg[level]=min(usg[level], dep);
else usg[level]=dep;
for (auto i:A[u]){
ll v = e[i].ss.ff^e[i].ss.ss^u;
if (v==p or black[i]) continue;
dfs(v, u, usg, level+e[i].ff, dep+1);
}
}
void cedfs(ll u, ll &mn, ll wsz){
ll centr = -1;
findcentroid(u,u, 0, centr, wsz);
assert(centr!=-1);
map<ll, ll> full, levs;
for (auto i:A[u]){
if (black[i]) continue;
ll v = e[i].ss.ff^e[i].ss.ss^u;
dfs(v, u, levs, e[i].ff, 1);
for (auto [length, tim]:levs){
// cout << length << "-" << tim << ' ';
if (full.count(k-length)){
mn=min(mn, full[k-length]+tim);
}
if (length==k){
mn=min(mn, tim);
}
}
// cout << ln;
for (auto [length, tim]:levs){
if (full.count(length)){
full[length]=min(full[length], tim);
}else{
full[length]=tim;
}
}
}
for (auto i:A[u]){
if (black[i]) continue;
black[i]=1;
ll v = e[i].ss.ff^e[i].ss.ss^u;
cedfs(v, mn, getsz(v, v));
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N; k=K;
e.resize(N-1);
A.resize(N);
for (ll i=0; i<n-1; i++){
A[H[i][0]].push_back(i);
A[H[i][1]].push_back(i);
e[i] = {L[i], {H[i][0], H[i][1]}};
}
black.resize(N);
sz.resize(N);
ll mn = 2e18;
cedfs(0, mn, getsz(0, 0));
return (mn==2e18?-1:mn);
}
