#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define ll long long
#define pb push_back
vector<bool>vt;
void dfs(ll u,vector<vector<ll>>&e,map<pair<ll,ll>,ll>&mp,vector<pair<ll,ll>>&v,vector<map<ll,ll>>&v5,int k,ll&ans){
if(vt[u]) return;
vt[u]=true;
v5[u][v[u].ff]=v[u].ss;
for(auto v1:e[u]){
if(vt[v1]) continue;
v[v1].ff=v[u].ff+mp[{u,v1}];
v[v1].ss=v[u].ss+1;
v5[v1][v[v1].ff]=v[v1].ss;
dfs(v1,e,mp,v,v5,k,ans);
for(auto jj:v5[v1]){
ll d=jj.ff,c=jj.ss;
if(v5[u].count(k-d+2*(v[u].ff))){
ans=min(ans,c-v[u].ss+v5[u][k-d+2*(v[u].ff)]-v[u].ss);
}
}
if(v5[u].size()<v5[v1].size()) swap(v5[u],v5[v1]);
for(auto jj:v5[v1]){
ll d=jj.ff,c=jj.ss;
if(v5[u].count(d)) v5[u][d]=min(v5[u][d],c);
else v5[u][d]=c;
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
vector<vector<ll>> e(N);
map<pair<ll,ll>, ll> mp;
for(ll i = 0; i < N - 1; i++) {
ll a = H[i][0], b = H[i][1], c = L[i];
e[a].pb(b);
e[b].pb(a);
mp[{a,b}] = c;
mp[{b,a}] = c;
}
vt.assign(N, false);
vector<map<ll,ll>> v5(N);
vector<pair<ll,ll>> v(N, {0,0});
ll ans = 1e18;
dfs(0, e, mp, v, v5, K, ans);
if(ans == 1e18) return -1;
else return ans;
}
