#include "race.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define pb push_back
using namespace std;
const int lim=1e6+5;
bool vis[lim];
vector<pii> ady[lim];
int mn[lim], sz[lim], ans, n, k;
pii dis[lim];
void rem(int u){
mn[dis[u].fi]=1e9;
vis[u]=true;
repa(v,ady[u]) if(!vis[v.fi]) rem(v.fi);
vis[u]=false;
}
void add(int u){
mn[dis[u].fi]=min(mn[dis[u].fi],dis[u].se);
vis[u]=true;
repa(v,ady[u]) if(!vis[v.fi]) add(v.fi);
vis[u]=false;
}
void calc(int u){
int x=1e9;
if(k>dis[u].fi) x=dis[u].se+mn[k-dis[u].fi];
vis[u]=true;
if(ans==-1 || ans>x) ans=x;
repa(v,ady[u]) if(!vis[v.fi]) calc(v.fi);
vis[u]=false;
}
void solve(int u, int r, int h, int e){
dis[u]={h,e};
vis[u]=true;
repa(v,ady[u]) if(!vis[v.fi]) solve(v.fi,r,min(lim,h+v.se),e+1);
vis[u]=false;
if(u==r){
repa(v,ady[u]) if(!vis[v.fi]) calc(v.fi), add(v.fi);
repa(v,ady[u]) if(!vis[v.fi]) rem(v.fi);
}
}
void pcalc(int u, int h){
sz[u]=1;
vis[u]=true;
repa(v,ady[u]) if(!vis[v.fi]) pcalc(v.fi,h+1), sz[u]+=sz[v.fi];
vis[u]=false;
}
int find_centroid(int u, int r){
vis[u]=true;
repa(v,ady[u]){
if(!vis[v.fi] && sz[v.fi]>sz[r]/2){
int x=find_centroid(v.fi,r);
vis[u]=false;
return x;
}
}
vis[u]=false;
return u;
}
void centroid(int u){
pcalc(u,0);
u = find_centroid(u,u);
solve(u,u,0,0);
vis[u]=true;
repa(v,ady[u]) if(!vis[v.fi]) centroid(v.fi);
vis[u]=false;
}
int best_path(int N, int K, int H[][2], int L[]){
rep(i,1,lim) mn[i]=1e9;
mn[0]=0;
rep(i,0,N-1){
ady[H[i][0]].pb({H[i][1],L[i]});
ady[H[i][1]].pb({H[i][0],L[i]});
}
n=N;
k=K;
ans=-1;
centroid(0);
if(ans==1e9) ans=-1;
return ans;
}
