#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
#define MAX_N 500000
const int inf=1e9;
int nn;
vector<ll>P, Order, ofst2;
vector<ll>ofst;
vector<vector<ll>>A;
vector<map<ll, ll>>Has;
map<pair<ll, ll>, ll>mp;
void pre(){
P.clear(), Order.clear(), ofst.clear(), ofst2.clear(), A.clear(), Has.clear(), mp.clear();
P.resize(nn+1), ofst.resize(nn+1), ofst2.resize(nn+1), A.resize(nn+1), Has.resize(nn+1);
}
void dfs(int u){
for(int i=0;i<A[u].size();i++){
int v=A[u][i];
if(v!=P[u])
P[v]=u, dfs(v);
}
Order.push_back(u);
}
int best_path(int n, int k, int H[][2], int L[]){
nn=n;
pre();
ll ans=inf;
for(int i=0;i<n-1;i++){
int u=H[i][0], v=H[i][1];
A[u].push_back(v);
A[v].push_back(u);
mp[{u, v}]=mp[{v, u}]=L[i];
}
dfs(0);
for(int kk=0;kk<n;kk++){
int u=Order[kk], mx=-1;
for(int i=0;i<A[u].size();i++){
int v=A[u][i];
if(v==P[u])
continue;
if(mx==-1 || Has[v].size()>Has[mx].size())
mx=v;
}
if(mx!=-1)
ofst[u]=ofst[mx]+mp[{u, mx}], ofst2[u]=ofst2[mx]+1, swap(Has[u], Has[mx]);
for(int i=0;i<A[u].size();i++){
int v=A[u][i];
if(v==P[u] || v==mx)
continue;
vector<array<ll, 2>>New;
for(auto it:Has[v]){
ll len=it.FF+ofst[v]+mp[{u, v}], need=it.SS+ofst2[v]+1;
if(Has[u].count(k-len-ofst[u]))
ans=min(ans, need+Has[u][k-len-ofst[u]]+ofst2[u]);
New.push_back({len, need});
}
for(int i=0;i<New.size();i++){
int len=New[i][0], need=New[i][1];
if(!Has[u].count(len-ofst[u]))
Has[u][len-ofst[u]]=need-ofst2[u];
else
Has[u][len-ofst[u]]=min(Has[u][len-ofst[u]], need-ofst2[u]);
}
}
Has[u][-ofst[u]]=-ofst2[u];
if(Has[u].count(k-ofst[u])){
ans=min(ans, Has[u][k-ofst[u]]+ofst2[u]);
}
}
if(ans==inf)
ans=-1;
return ans;
}
