#include "race.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define endl '\n'
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ar array
const int MOD = 1e9 + 7,INF = 1e9, N = 2e5 + 5;
int n , k, ans = INF;
vector <vector<pair<int,int>>> g;
vector <int> del, sub_sz;
vector <int> mp(10000, INF);
vector <pair<int,int>> sum;
void dfs(int v,int p){
sub_sz[v] = 1;
for(auto [i , c] : g[v]){
if(i == p || del[i]) continue;
dfs(i , v);
sub_sz[v] += sub_sz[i];
}
}
int cent(int v, int p, int m){
// cout<<"HERE "<<v<<endl;
for(auto [i , c] : g[v]){
if(sub_sz[i] * 2 > m && !del[i] && i != p){
return cent(i, v, m);
}
}
return v;
}
void bfs(int x, int p){
// cout<<x<<' ' << p<<endl;
for(auto [i , c] : g[x]){
if(i == p || del[i]) continue;
sum[i].ff = sum[x].ff + c;
sum[i].ss = sum[x].ss + 1;
int h = k - sum[i].ff;
if(h >= 0){
ans = min(ans , mp[h] + sum[i].ss);
}
bfs(i, x);
}
}
void add(int x , int p){
for(auto [i , c] : g[x]){
if(i == p || del[i]) continue;
mp[sum[i].ff] = min(mp[sum[i].ff] , sum[i].ss);
add(i , x);
}
}
void dec(int v , int m){
// cout<<v<<endl;
dfs(v , v);
// for(int i = 0;i < n;i++){
// cout<<sub_sz[i]<<' ';
// }
// cout<<endl;
int cen = cent(v, v , m);
// cout<<cen<<endl;
mp[0] = 0;
del[cen] = 1;
for(auto [i , c] : g[cen]){
if(del[i]) continue;
sum[i].ff = c;
sum[i].ss = 1;
bfs(i , i);
mp[sum[i].ff] = min(mp[sum[i].ff] , sum[i].ss);
int h = k - sum[i].ff;
if(h >= 0){
ans = min(ans , mp[h] + sum[i].ss);
}
add(i, i);
// cout<<endl;
}
mp.clear();
mp.resize(10000, INF);
sum.clear();
sum.resize(N + 1);
sub_sz.clear();
sub_sz.resize(N + 1, 0);
for(auto [i , c] : g[cen]){
if(del[i]) continue;
dec(i, sub_sz[i]);
}
}
int best_path(int N1, int K, int H[][2], int L[]){
n = N1;
k = K;
// if(n == 100){
// while(true);
// }
g.resize(n + 1);
del.resize(n + 1);
sub_sz.resize(n + 1);
sum.resize(n + 1);
for(int i = 0;i < n - 1;i++){
int a = H[i][0], b = H[i][1] , c = L[i];
g[a].pb({b , c});
g[b].pb({a , c});
}
dec(1, n);
if(ans == INF){
return -1;
}
return ans;
}
