#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#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,best;
int dfs(int node,int p,bool flag=0,int d=0,ll h=0){
s[node]=1;
if(flag)mymap[h].insert(d);
for(auto it:vec[node])
if(it.fi!=p&&!dead[it.fi])
s[node]+=dfs(it.fi,node,flag,d+1,h+it.se);
return s[node];
}
void remove_add(int node,int p,int d,ll h){
best[h].insert(d);
auto it=mymap[h].find(d);
mymap[h].erase(it);
if(mymap[h].empty())mymap.erase(h);
for(auto it:vec[node])
if(it.fi!=p&&!dead[it.fi])
remove_add(it.fi,node,d+1,h+it.se);
}
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);
//cerr<<n<<","<<node<<"\n";
int r=find_cetroid(node,node);
//cerr<<"centroid: "<<r<<"\n";
mymap.clear();
dfs(r,r,1);
/*cerr<<"sz(mymap): "<<mymap.size()<<"\n";
for(auto it:mymap){
cerr<<"dist: "<<it.fi<<"\n";
for(auto it2:it.se)
cerr<<it2<<" ";
cout<<"\n";
}*/
for(auto it:vec[r]){
if(dead[it.fi])continue;
remove_add(it.fi,r,1,it.se);
for(auto it3:best){
if(it3.fi>k)break;
//cerr<<"it3.fi : "<<it3.fi<<"\n";
//cerr<<"k-it3.fi: "<<k-it3.fi<<"\n";
if(mymap.count(k-it3.fi))ans=min(ans,(ll)*(mymap[k-it3.fi].begin())+*(it3.se.begin()));
}
//cerr<<"subtree : "<<it.fi<<"\n";
//cerr<<"ans : "<<ans<<"\n";
for(auto it3:best)
for(auto it2:it3.se)
mymap[it3.fi].insert(it2);
best.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[])
{
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);
}
