#include "race.h"
#include<bits/stdc++.h>
using namespace std ;
const int NN = 1e4 + 7 ;
int n , k ;
int ans = 100000000 ;
vector<pair<int , int > > adj[NN] ;
int hei[NN] , ldr[NN] , sz[NN];
int fr[NN] , ls[NN] , ver[NN];
map<int , int > anss[NN] ;
int t = 1;
int dfz(int x , int p , int h, int l = 1 ){
ver[t] = x ;
fr[x] = t++ ;
int ret = 1;
hei[x] = h ;
ldr[x] = l ;
for(auto u : adj[x]){
if(u.first==p)continue ;
ret+=dfz(u .first, x , h+ u.second , l+1 ) ;
}
ls[x] = t++ ;
return sz[x] = ret ;
}
int dfs(int x , int p , bool keep){
int big = 0 ;
for(auto u : adj[x]){
if(u.first==p)continue ;
if(sz[u.first] > sz[big]){
big = u.first ;
}
}
for(auto u : adj[x]){
if(u.first ==p || u.first ==big)continue ;
dfs(u.first, x , 0) ;
}
if(big){
dfs(big , x , 1 ) ;
}
anss[hei[x]][ldr[x]]++;
for(auto u : adj[x]){
if(u.first==p || u.first == big)continue ;
vector<int> v ;
for(int j = fr[u.first] ; j < ls[u.first] ;j ++ ){
if( ver[j] ){
int he = hei[ver[j]] ;
int dl = ldr[ver[j]] ;
int drem = k - (hei[ver[j] - hei[x] ]) ;
if( drem <=0)continue ;
for(auto u : anss[ hei[x] + drem ]){
if(u.second){
ans = min(ans , u.first - ldr[x] + ldr[ver[j]] - ldr[x]) ;
}
}
v.push_back(j) ;
}
}
for(auto e : v){
anss[hei[ver[e]]][ ldr[ver[e]] ]++ ;
}
}
for(auto u: anss[hei[x] + k] ){
if(u.second){
ans = min(ans , u.first - ldr[x] ) ;
}
}
if(!keep){
for(int i = fr[x] ; i < ls[x] ; i++){
anss[hei[ver[i]]][ldr[ver[i]]] -- ;
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N ;
k = K ;
for(int i = 0 ;i < n-1 ;i++){
adj[H[i][0]+1].push_back({H[i][1]+1 , L[i]}) ;
adj[H[i][1]+1].push_back({H[i][0]+1, L[i]}) ;
}
dfz(1 , 1 , 0) ;
dfs(1 , 1 , 0) ;
if(ans==100000000) ans = -1 ;
return ans ;
}
