#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
vector<pair<int,int> >graf[N];
int pod[N];
pair<pair<int,int>,pair<int,int> >t[1000*1000+10];
bool vis[N];
int cn;
int res=INT_MAX;
int dfspod(int v,int o){
int res=0;
for(auto u:graf[v]){
if(vis[u.fi]||u.fi==o) continue;
res+=dfspod(u.fi,v);
}
return res+1;
}
void dfs(int v,int o,int s){
bool b=1;
pod[v]=0;
for(auto u:graf[v]){
if(vis[u.fi]||o==u.fi) continue;
dfs(u.fi,v,s);
pod[v]+=pod[u.fi];
if(pod[u.fi]>s/2) b=0;
}
pod[v]++;
if(s-pod[v]>s/2) b=0;
if(b) cn=v;
}
void dfs2(int v,int o,int g,int odl,bool b,int k){
if(g>1000*1000) return;
if(b==0) t[g].fi.fi=0,t[g].fi.se=0,t[g].se.fi=0,t[g].se.se=0;
else if(t[g].fi.fi>odl||t[g].fi.fi==0) t[g].fi={odl,k};
for(auto u:graf[v]){
if(vis[u.fi]||o==u.fi) continue;
dfs2(u.fi,v,g+u.se,odl+1,b,k);
}
}
void dfs3(int v,int o,int g,int odl,int k){
if(g>1000*1000) return;
if(t[g].fi.se!=k&&(t[g].se.fi>odl||t[g].se.fi==0)) t[g].se={odl,k};
for(auto u:graf[v]){
if(vis[u.fi]||o==u.fi) continue;
dfs3(u.fi,v,g+u.se,odl+1,k);
}
}
void dfs_wyn(int v,int o,int g,int odl,int k,int kk){
if(g>k) return;
if(g==k) res=min(res,odl);
if(t[k-g].fi.se!=kk&&t[k-g].fi.fi!=0) res=min(res,t[k-g].fi.fi+odl);
if(t[k-g].se.se!=kk&&t[k-g].se.fi!=0) res=min(res,t[k-g].se.fi+odl);
for(auto u:graf[v]){
if(vis[u.fi]||o==u.fi) continue;
dfs_wyn(u.fi,v,g+u.se,odl+1,k,kk);
}
}
void decomp(int v,int k){
if(vis[v]) return;
int s=dfspod(v,v);
dfs(v,v,s);
for(auto u:graf[cn]){
if(vis[u.fi]) continue;
dfs2(u.fi,cn,u.se,1,1,u.fi);
}
for(auto u:graf[cn]){
if(vis[u.fi]) continue;
dfs3(u.fi,cn,u.se,1,u.fi);
}
for(auto u:graf[cn]){
if(vis[u.fi]) continue;
dfs_wyn(u.fi,cn,u.se,1,k,u.fi);
}
for(auto u:graf[cn]){
if(vis[u.fi]) continue;
dfs2(u.fi,cn,u.se,1,0,u.fi);
}
int cc=cn;
vis[cc]=1;
for(auto u:graf[cc]) decomp(u.fi,k);
}
int best_path(int n,int k,int h[][2],int l[]){
for(int i=0;i<=n-2;i++) h[i][0]++,h[i][1]++,graf[h[i][0]].push_back({h[i][1],l[i]}),graf[h[i][1]].push_back({h[i][0],l[i]});
decomp(1,k);
if(res==INT_MAX) return -1;
return res;
}
