#include "race.h"
#include <bits/stdc++.h>
using namespace std ;
#define ff first
#define ss second
const int Ne = 2e5 + 5 ;
const int inf = 1e9 ;
template <class T>
bool chmax( T& x , const T& y ){
bool f = 0 ;
if ( x < y ) x = y , f = 1 ;
return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
bool f = 0 ;
if ( x > y ) x = y , f = 1 ;
return f ;
}
int n , k , ans = inf , sz[Ne] , mx ;
bool vis[Ne] ;
vector <int> mp ;
vector <pair <int , int>> g[Ne] ;
vector <pair <int , int>> vec ;
int fsz ( int v , int p = -1 ){
sz[v] = 1 ;
for ( auto to : g[v] ){
if ( to.ff != p && !vis[to.ff] ) fsz(to.ff,v) , sz[v] += sz[to.ff] ;
} return sz[v] ;
}
int centroid ( int v , int s , int p = -1 ){
for ( auto to : g[v] ){
if ( sz[to.ff] >= s && to.ff != p && !vis[to.ff] ) return centroid( to.ff , s , v ) ;
} return v ;
}
void dfs( int v , int d , int s , int p , int i ){
if ( s > k ) return ;
chmin ( ans , d+mp[k-s] ) ;
chmax ( mx , s ) ;
for ( auto to : g[v] ) if ( to.ff != p && !vis[to.ff] ) dfs( to.ff , d+1 , s+to.ss , v , i ) ;
}
void upd( int v , int d , int s , int p , int i ){
if ( s > k ) return ;
chmin ( mp[s] , d ) ;
for ( auto to : g[v] ) if ( to.ff != p && !vis[to.ff] ) upd( to.ff , d+1 , s+to.ss , v , i ) ;
}
void go ( int v ){
v = centroid( v , fsz(v)/2 ) ;
vis[v] = 1 ; mx = 0 ;
for ( auto to : g[v] ){
dfs ( to.ff , 1 , to.ss , -1 , to.ff ) ;
upd ( to.ff , 1 , to.ss , -1 , to.ff ) ;
} chmin ( ans , mp[k] ) ;
for ( int i = 0 ; i <= mx ; i ++ ) mp[i] = INT_MAX - n ;
for ( auto to : g[v] ) if ( !vis[to.ff] ) go (to.ff) ;
}
int best_path(int N, int K, int h[][2], int l[]){
n = N , k = K ;
mp.resize(k+1 , INT_MAX-n);
for ( int i = 0 ; i < n-1 ; i ++ ){
g[h[i][0]].push_back({h[i][1],l[i]}) ;
g[h[i][1]].push_back({h[i][0],l[i]}) ;
}
go(1) ;
return (ans == inf) ? -1 : ans ;
}
