#include "race.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
using pii = pair < int, int >;
map < int, int > x, y;
vector < vector < pair < int, int > > > to;
int n, k, sz[N], res = 1e9;
bool blocked[N];
int get_size(int u, int p){
sz[u] = 1;
for( pii v : to[u] ){
if( blocked[v.first] || v.first == p ) continue;
sz[u] += get_size( v.first, u );
}
return sz[u];
}
int get_center( int u, int p, int comp_size ){
for( pii v : to[u] ){
if( blocked[v.first] || v.first == p ) continue;
if( sz[v.first] > comp_size ) return get_center(v.first, u, comp_size);
}
return u;
}
void dfs(int u, int p, int len, int dis){
if( y.find( len ) == y.end() ) y[len] = dis;
else{
y[len] = min( dis, y[len] );
}
for( pii v : to[u] ){
if( blocked[v.first] || v.first == p ) continue;
dfs( v.first, u, len + v.second, dis + 1 );
}
}
void decomp(int u){
u = get_center(u, -1, get_size(u, -1)/2);
x.clear();
x[0] = 0;
for( pii v : to[u] ){
if( blocked[v.first] ) continue;
y.clear();
dfs( v.first, u, v.second, 1 );
for( pii now : y ){
if( x.find( k-now.first ) != x.end() ){
res = min( res, x[k-now.first] + now.second );
}
}
for( pii now : y ){
if( x.find( now.first ) == x.end() ) x[now.first] = now.second;
else{
x[now.first] = min( x[now.first], now.second );
}
}
}
blocked[u] = 1;
for( pii v : to[u] ){
if( blocked[v.first] ) continue;
decomp( v.first );
}
}
int best_path(int NN, int K, int H[][2], int L[]){
n = NN, k = K;
to.resize(n);
for(int i = 0 ; i < n-1 ; i++){
to[ H[i][0] ].push_back( make_pair( H[i][1], L[i] ) );
to[ H[i][1] ].push_back( make_pair( H[i][0], L[i] ) );
}
decomp( 0 );
return res == 1e9 ? -1 : res;
}
