#include <bits/stdc++.h>
#include "race.h"
#define fi first
#define se second
#define ll long long
using namespace std;
const int N = 2e5 + 7;
const int NN = 1e6 + 7;
const int mod = 1e9 + 7;
int n,k;
int ans = 1e9;
bool used[N];
int sz[N];
int m[NN];
vector < pair < int , int > > v[N];
void dfs( int x , int p , int d , vector < pair < int , int > > &t , int sum )
{
if( sum > k )return;
t.push_back({sum , d});
for( auto y : v[x] ){
if( y.fi != p && !used[y.fi] ){
dfs(y.fi , x , d + 1 , t , sum + y.se);
}
}
}
int centr( int x , int p , int n )
{
for( auto y : v[x] ){
if( y.fi != p && !used[y.fi] && sz[y.fi] > n / 2 ){
return centr(y.fi , x , n);
}
}
return x;
}
void siz( int x , int p )
{
sz[x] = 1;
for( auto y : v[x] ){
if( y.fi == p || used[y.fi] )continue;
siz(y.fi , x);
sz[x] += sz[y.fi];
}
}
vector < int > g;
vector < pair < int , int > > t;
void solve( int x )
{
siz(x , x);
g.clear();
for( auto y : v[x] ){
if(used[y.fi]) continue;
t.clear();
dfs(y.fi , x , 1 , t , y.se);
for( auto it : t ){
if( it.fi < k ){
if( m[k - it.fi] != mod ){
ans = min(ans , m[k - it.fi] + it.se);
}
}else if( it.fi == k ){
ans = min(ans , it.se);
}
}
for( auto it : t ){
if( it.fi >= k )continue;
m[it.fi] = min( m[it.fi] , it.se );
g.push_back(it.fi);
}
}
for( auto y : g ){
m[y] = mod;
}
used[x] = true;
for( auto y : v[x] ){
if( !used[y.fi] ){
solve(centr(y.fi , x , sz[y.fi]));
}
}
}
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];
int y = H[i][1];
int z = L[i];
x++,y++;
v[x].push_back({y , z});
v[y].push_back({x , z});
}
for( int i = 0; i < NN; i++ ){
m[i] = mod;
}
siz(1 , 1);
solve(centr(1 , 1 , n));
if( ans == 1e9 )ans = -1;
return ans;
}
