#include "race.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=2e5+5;
int sz[N],dist[2][N],ans,u,v,n,k,vis[N],H;
vector<int>C[N];
pair<int,int> fix[N*10];
vector<pair<int,int> > V[N];
void find_size(int u,int p,int d,int d1,int h){
sz[u]=1;
dist[0][u]=d1;
dist[1][u]=d;
for(int i=0;i<V[u].size();i++){
if(!vis[V[u][i].f] && V[u][i].f!=p){
find_size(V[u][i].f,u,d+V[u][i].s,d1+1,h);
sz[u]+=sz[V[u][i].f];
}
}
}
int find_centroid(int u,int p,int Sz){
for(int i=0;i<V[u].size();i++){
if(!vis[V[u][i].f] && V[u][i].f!=p && Sz/2<sz[V[u][i].f]) {
return find_centroid(V[u][i].f,u,Sz);
}
}
return u;
}
void dfs(int u,int p,int t){
if(k<dist[1][u]) return;
if(t==0){
if(fix[k-dist[1][u]].f==H) ans=min(ans,dist[0][u]+fix[k-dist[1][u]].s);}
else if(t==1){
if(fix[dist[1][u]].f!=H) fix[dist[1][u]].f=H ,fix[dist[1][u]].s = dist[0][u];
else fix[dist[1][u]].s=min(dist[0][u],fix[dist[1][u]].s);
}
for(int i=0;i<V[u].size();i++){
if(!vis[V[u][i].f] && V[u][i].f!=p)dfs(V[u][i].f,u,t);
}
}
void new_tree(int u,int p,int h){
find_size(u,0,0,0,h);
int c=find_centroid(u,0,sz[u]);
find_size(c,0,0,0,h);
vis[c]=h;
fix[0].f=c;
H=c;
for(int i=0;i<V[c].size();i++){
if(!vis[V[c][i].f]){
dfs(V[c][i].f,c,0);
dfs(V[c][i].f,c,1);
}
}
for(int i=0;i<V[c].size();i++){
if(!vis[V[c][i].f]) new_tree(V[c][i].f,c,h+1);
}
}
int best_path(int n, int K, int H[][2], int L[]) {
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
k=K;
for(int i=0;i<n-1;i++){
u=H[i][0]; v=H[i][1];
u++; v++;
int w=L[i];
V[u].push_back({v,w});
V[v].push_back({u,w});
}
ans=4e5;
new_tree(1,0,1);
if(ans>n)ans=-1;
return ans;
}
