#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, ans;
ll k;
vector< vector< pair<int,int> > > grp;
vector<int> ssize, h;
vector<ll> pref;
int dfs_prec ( int v, int p )
{
for ( auto& [to,w] : grp[v] )
if ( to != p )
{
h[to] = h[v] + 1;
pref[to] = pref[v] + w;
ssize[v] += dfs_prec( to, v );
}
return ssize[v];
}
vector< vector<int>* > ver;
map<ll,int> mini;
void upd ( int in, int v )
{
if ( pref[in] + k == pref[v] )
ans = min( ans, h[v] - h[in] );
else if ( pref[v] - pref[in] < k && mini.count( pref[in] + k - (pref[v] - pref[in]) ) )
ans = min( ans, ( h[v] - h[in] ) + ( mini[ pref[in] + k - (pref[v] - pref[in]) ] - h[in] ) );
}
void add ( int v )
{
if ( mini.count( pref[v] ) )
mini[ pref[v] ] = min( mini[ pref[v] ], h[v] );
else
mini[ pref[v] ] = h[v];
}
void dfs ( int v, int p, bool keep )
{
//cout << "dfs: " << v << ' ';
int bigs = -1, bigv = -1;
for ( auto& [to,w] : grp[v] )
if ( to != p && ssize[to] > bigs )
{
bigs = ssize[to];
bigv = to;
}
//cout << bigs << ' ' << bigv << '\n';
for ( auto& [to,w] : grp[v] )
if ( to != p && to != bigv )
dfs( to, v, false );
if ( bigv == -1 )
ver[v] = new vector<int>();
else
{
dfs( bigv, v, true );
ver[v] = ver[bigv];
}
ver[v]->push_back( v );
for ( auto& [to,w] : grp[v] )
if ( to != p && to != bigv )
{
for ( auto& el : *ver[to] )
upd( v, el );
for ( auto& el : *ver[to] )
{
ver[v]->push_back( el );
add( el );
}
}
if ( mini.count( pref[v] + k ) )
ans = min( ans, mini[ pref[v] + k ] - h[v] );
mini[ pref[v] ] = h[v];
/*cout << "mini " << v << ": ";
for ( auto& [x,y] : mini )
cout << "(" << x << ' ' << y << ") ";
cout << '\n';*/
if ( !keep )
mini.clear();
}
int best_path ( int n_, int k_, int(*h_)[2], int* l_ )
{
n = n_;
k = k_;
grp.assign( n, vector< pair<int,int> >() );
for ( int i=0; i<n-1; i++ )
{
grp[ h_[i][0] ].push_back({ h_[i][1], l_[i] });
grp[ h_[i][1] ].push_back({ h_[i][0], l_[i] });
}
ssize.assign( n, 1 );
h.assign( n, 1 );
pref.assign( n, 0 );
dfs_prec( 0, -1 );
ver.assign( n, nullptr );
mini.clear();
ans = 2e9;
dfs( 0, -1, false );
return ans == 2e9 ? -1 : ans;
}
