#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;
map <int,int> mp;
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){
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 && h <= k){
if(h != 0 && mp[h] == 0){
}
else{
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;
if(sum[i].ff <= k && sum[i].ff >= 0){
if(mp[sum[i].ff] == 0 && sum[i].ff != 0) mp[sum[i].ff] = INF;
mp[sum[i].ff] = min(mp[sum[i].ff] , sum[i].ss);
}
add(i , x);
}
}
void dec(int v){
dfs(v , v);
int m = sub_sz[v];
int cen = cent(v, v , m);
mp.clear();
mp[0] = 0;
for(auto [i , c] : g[cen]){
if(del[i] && i == cen) continue;
sum[i].ff = c;
sum[i].ss = 1;
bfs(i , cen);
int h = k - sum[i].ff;
if(h >= 0 && h <= k){
if(h != 0 && mp[h] == 0){
}
else {
ans = min(ans , mp[h] + sum[i].ss);
}
}
if(sum[i].ff <= k){
if(mp[sum[i].ff] == 0 && sum[i].ff != 0) mp[sum[i].ff] = INF;
mp[sum[i].ff] = min(mp[sum[i].ff] , sum[i].ss);
}
add(i, cen);
}
del[cen] = 1;
for(auto [i , c] : g[cen]){
if(del[i]) continue;
dec(i);
}
}
int best_path(int N1, int K, int H[][2], int L[]){
n = N1;
k = K;
ans = INF;
g.clear();
del.clear();
sub_sz.clear();
g.resize(n);
del.resize(n);
sub_sz.resize(n);
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(0);
if(ans == INF){
return -1;
}
return ans;
}
