#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;
const int maxn = 3e5 + 10;
const int maxk = 1e6 + 10;
vector<pair< int, ll>> adj[maxn];
vector<int> removed( maxn ), sub( maxn ), melhor( maxk, maxk );
int N, K;
int resp = maxk;
void dfsInit( int cur, int pai ){
sub[cur] = 1;
for( auto [viz, d] : adj[cur] ) if( viz != pai && !removed[viz] ){
dfsInit( viz, cur );
sub[cur] += sub[viz];
}
}
int findCentroid( int cur, int pai, int tam ){
for( auto [viz, d] : adj[cur] ) if( viz != pai && !removed[viz] ){
if( sub[viz] > tam/2 ) return findCentroid(viz, cur, tam);
}
return cur;
}
void dfs( int cur, int pai, int nivel, int dist, int t ){
if( dist > K ) return;
if( t == 1 ) resp = min( resp, nivel + melhor[K - dist] );
if( t == 2 ) melhor[dist] = min( melhor[dist], nivel );
if( t == 3 ) melhor[dist] = maxk;
for( auto [viz, d] : adj[cur] ) if( viz != pai && !removed[viz] ){
dfs( viz, cur, nivel + 1, dist + d, t );
}
}
void decompose( int node ){
dfsInit( node, node );
int centroid = findCentroid( node, node, sub[node] );
bug(centroid)
melhor[0] = 0;
for( auto [viz, d] : adj[centroid] ) if( !removed[viz] ){
dfs( viz, centroid, 1, d, 1 );
dfs( viz, centroid, 1, d, 2 );
}
dfs( centroid, centroid, 0, 0, 3 );
removed[centroid] = 1;
for( auto[ viz, d ] : adj[centroid] ) if( !removed[viz] ) decompose( viz );
}
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]].push_back({ h[i][1], l[i] });
adj[h[i][1]].push_back({ h[i][0], l[i] });
}
decompose(0);
if( resp == maxk ) resp = -1;
return resp;
}
