#include<bits/stdc++.h>
#include "race.h"
#define fi first
#define se second
using namespace std;
const int NN=2e5;
const int INF=1e9+7;
struct Poss
{
int val[2],g[2];
Poss()
{
val[0]=val[1]=INF;
g[0]=g[1]=0;
}
void operator+=(pair<int,int> oth)
{
int vv=oth.fi,gg=oth.se;
if(vv<val[0] && g[0]!=gg)
{
val[1]=val[0];
g[1]=g[0];
val[0]=vv;
g[0]=gg;
}
else if(vv<val[0])
val[0]=vv;
else if(vv<val[1] && g[0]!=gg)
{
val[1]=vv;
g[1]=gg;
}
return;
}
int get(int x)
{
return (x==g[0] ? val[1]:val[0]);
}
};
int k;
vector<pair<int,int>> e[NN+10];
bool vis[NN+10];
int siz[NN+10];
map<int,Poss> mp;
void dfs_siz(int x,int p)
{
siz[x]=1;
for(auto v:e[x])
{
if(!vis[v.fi] && v.fi!=p)
{
dfs_siz(v.fi,x);
siz[x]+=siz[v.fi];
}
}
return;
}
int centro(int x,int p,int s_all)
{
for(auto v:e[x])
{
if(vis[v.fi] || v.fi==p)
continue;
int c=centro(v.fi,x,s_all);
if(c!=-1)
return c;
}
if(2*siz[x]>=s_all)
return x;
return -1;
}
int dfs(int x,int p,int d1,int d2,int id)
{
int ans=INF;
ans=min(ans,d2+mp[k-d1].get(id));
mp[d1]+=make_pair(d2,id);
for(auto v:e[x])
{
if(vis[v.fi] || v.fi==p)
continue;
ans=min(ans,dfs(v.fi,x,min(INF,d1+v.se),d2+1,id));
}
return ans;
}
int solve(int x)
{
int ans=INF;
dfs_siz(x,-1);
x=centro(x,-1,siz[x]);
vis[x]=true;
mp.clear();
mp[0]+=make_pair(0,x);
for(auto v:e[x])
{
if(!vis[v.fi])
ans=min(ans,dfs(v.fi,x,v.se,1,v.fi));
}
for(auto v:e[x])
{
if(!vis[v.fi])
ans=min(ans,solve(v.fi));
}
return ans;
}
int best_path(int N,int K,int H[][2],int L[])
{
k=K;
for(int i=0;i<N-1;i++)
{
e[H[i][0]].push_back({H[i][1],L[i]});
e[H[i][1]].push_back({H[i][0],L[i]});
}
int ans=solve(0);
return (ans>=INF ? -1:ans);
}
