#include<bits/stdc++.h>
#include "race.h"
using namespace std;
long long n , k , mn = 1e9 , dis [200005] , dp [200005] , in [200005] , ot [200005] , siz [200005] , tmm;
int H [200005][2] , L [200005];
vector < int > ord;
vector < pair < int , int > > gr [200005];
map < long long , multiset < int > > cnt;
void go ( int x , int p )
{
in [x] = tmm ++;
dp [x] = dp [p] + 1;
siz [x] = 1;
ord . push_back ( x );
for ( auto pr : gr [x] )
{
long long u = pr . first , c = pr . second;
if ( u == p ) continue;
dis [u] = dis [x] + c;
go ( u , x );
siz [x] += siz [u];
}
ot [x] = tmm;
}
void dfs ( int x , int p , int keep )
{
int mx = -1 , big = -1;
for ( auto pr : gr [x] )
{
int u = pr . first;
if ( u == p ) continue;
if ( mx < siz [u] )
{
mx = siz [u];
big = u;
}
}
for ( auto pr : gr [x] )
{
int u = pr . first;
if ( u == p || u == big ) continue;
dfs ( u , x , 0 );
}
if ( big != -1 ) dfs ( big , x , 1 );
for ( auto pr : gr [x] )
{
int u = pr . first;
if ( u == p || u == big ) continue;
for ( int j = in [u] ; j < ot [u] ; j ++ )
{
int v = ord [j];
long long dif = dis [v] - dis [x];
if ( cnt [ k - dif + dis [x] ] . size () == 0 ) continue;
int bst = * cnt [ k - dif + dis [x] ] . begin ();
mn = min ( mn , dp [v] + bst - 2 * dp [x] );
}
for ( int j = in [u] ; j < ot [u] ; j ++ )
{
int v = ord [j];
cnt [ dis [v] ] . insert ( dp [v] );
}
}
if ( cnt [ k + dis [x] ] . size () )
{
int bst = * cnt [ k + dis [x] ] . begin ();
mn = min ( mn , bst - dp [x] );
}
cnt [ dis [x] ] . insert ( dp [x] );
if ( keep == 0 )
{
for ( int j = in [x] ; j < ot [x] ; j ++ )
{
int v = ord [j];
cnt [ dis [v] ] . erase ( cnt [ dis [v] ] . lower_bound ( dp [v] ) );
}
}
}
int best_path( int N , int K , int H [][2] , int L [] )
{
n = N , k = K;
for( int i = 0 ; i < n - 1 ; i ++ )
{
int x = H [i][0] + 1 , y = H [i][1] + 1;
gr [x] . push_back ( { y , L [i] } );
gr [y] . push_back ( { x , L[i] } );
}
go ( 1 , 0 );
dfs ( 1 , 0 , 0 );
if ( mn != 1e9 ) return mn;
else return -1;
}
