#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define fi first
#define se second
#define ll long long
bool dead[200005];
int s[200005],n,k;
ll ans=LLONG_MAX;
vector<vector<pair<int,int> > > vec;
map<ll,multiset<int> > mymap;
vector<map<ll,int> > best;
int dfs(int node,int p,int s_p,bool flag=0,int d=0,ll h=0){
if(flag&&(s_p!=-1)){
if(best[s_p].count(h))best[s_p][h]=min(best[s_p][h],d);
else best[s_p][h]=d;
}
s[node]=1;
for(auto it:vec[node])
if(it.fi!=p&&!dead[it.fi])
s[node]+=dfs(it.fi,node,((!d)?it.fi:s_p),flag,d+1,h+it.se);
return s[node];
}
int find_cetroid(int node,int p){
for(auto it:vec[node])
if(it.fi!=p&&!dead[it.fi]&&s[it.fi]>(n/2))
return find_cetroid(it.fi,node);
return node;
}
void solve(int node){
n=dfs(node,node,-1);
int r=find_cetroid(node,node);
mymap.clear();
dfs(r,r,-1,1);
for(auto it:vec[r]){
if(dead[it.fi])continue;
for(auto it2:best[it.fi])
mymap[it2.fi].insert(it2.se);
}
for(auto it:vec[r]){
if(dead[it.fi])continue;
for(auto it3:best[it.fi]){
if(it3.fi>k)break;
if(!mymap.count(k-it3.fi))continue;
auto hk=mymap[k-it3.fi].begin();
if((best[it.fi].count(k-it3.fi))&&((*hk)==best[it.fi][k-it3.fi]))hk++;
if(hk!=mymap[k-it3.fi].end())ans=min(ans,(ll)(*hk)+it3.se);
}
if(best[it.fi].count(k))ans=min(ans,(ll)best[it.fi][k]);
best[it.fi].clear();
}
dead[r]=1;
for(auto it:vec[r])
if(!dead[it.fi])
solve(it.fi);
}
int best_path(int N, int K, int H[][2], int L[])
{
best.resize(N);
k=K;
vec.resize(N);
for (int i = 0; i < N-1; ++i)
{
vec[H[i][0]].push_back({H[i][1],L[i]});
vec[H[i][1]].push_back({H[i][0],L[i]});
}
solve(0);
return ((ans==LLONG_MAX)?(-1):ans);
}
