#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(a,b,c) for(int a=b;a<c;a++)
#define PB push_back
#define F first
#define S second
#define LSOne(s) ((s)&(-s))
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
int inf=1000000010;
int n,k,sv=0,ev=0,m;
vector<pii> a;
vi s,st,en,depth,length,vis;
vii p,b,c;
int ans=inf;
void dfs(int x){
st[x]=sv++;
for(auto u:a[x])if(p[x][0]!=u.F){
p[u.F][0]=x;
depth[u.F]=depth[x]+1;
length[u.F]=length[x]+u.S;
dfs(u.F);
s[x]+=s[u.F];
}
en[x]=ev++;
}
int centroid(int x){
for(auto u:a[x])if(!vis[u.F]&&s[u.F]>s[x]/2){
s[x]-=s[u.F];
s[u.F]+=s[x];
return centroid(u.F);
}
return x;
}
void decompose(int x){
for(auto u:a[x])if(!vis[u.F]){
int y=centroid(u.F);
b[x].PB(y);
vis[y]=1;
decompose(y);
}
}
bool ances(int x,int y){
if(y==-1)return 1;
if(st[x]>=st[y]&&en[x]<=en[y])return 1;
return 0;
}
pi dist(int x,int y){
if(ances(x,y)||ances(y,x))
return {abs(depth[x]-depth[y]),abs(length[x]-length[y])};
int z=y;
for(int i=m-1;i>=0;i--)if(!ances(x,p[y][i]))y=p[y][i];
y=p[y][0];
return {depth[x]+depth[z]-2*depth[y],length[x]+length[z]-2*length[y]};
}
void solve(int x){
unordered_map<int,int> mp;
c[x].PB(x);
for(auto u:b[x]){
solve(u);
unordered_map<int,int> tmp;
for(auto v:c[u]){
pi r=dist(v,x);
if(r.S>k)continue;
if(r.S==k){
ans=min(ans,r.F);
continue;
}
if(tmp[r.S]==0)tmp[r.S]=r.F;
else tmp[r.S]=min(tmp[r.S],r.F);
if(mp[k-r.S]!=0)ans=min(ans,mp[k-r.S]+r.F);
}
for(auto v:tmp){
if(mp[v.F]==0)mp[v.F]=v.S;
else mp[v.F]=min(mp[v.F],v.S);
}
for(auto u:c[u])c[x].PB(u);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;k=K;
m=log2(n)+2;
a.resize(n);
REP(i,0,n-1){
a[H[i][0]].PB({H[i][1],L[i]});
a[H[i][1]].PB({H[i][0],L[i]});
}
p.resize(n,vi(m,-1));s.resize(n,1);st.resize(n);en.resize(n);
depth.resize(n,0);length.resize(n,0);vis.resize(n,0);
vis.resize(n,0);b.resize(n);c.resize(n);
dfs(0);
REP(j,1,m)REP(i,0,n)if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];
int x=centroid(0);
vis[x]=1;
decompose(x);
solve(x);
if(ans==inf)return -1;
return ans;
}
