//#include "race.h"
//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 5e5+100;
int K, sz[MAXN];
vector<pii> g[MAXN];
bool vis[MAXN];
void centroid(int v, int p, int csz, int& ans){
sz[v] = 1; bool is = true;
for(auto [u, w] : g[v]){
if(u == p || vis[u]) continue;
centroid(u, v, csz, ans);
sz[v] += sz[u];
if(sz[u] * 2 > csz){
is = false;
}
}
if((csz - sz[v]) * 2 <= csz && is){
ans = v;
}
}
void dfs(int v, int p, int d, int len, map<int, int>& m){
if(d > K) return;
if(!m.count(d) || m[d] > len){
m[d] = len;
}
for(auto [u, w] : g[v]){
if(u == p || vis[u])
continue;
dfs(u, v, d + w, len + 1, m);
}
}
int solve(int v, int p, int csz){
centroid(v, p, csz, v);
int ans = INT_MAX;
map<int, int> m;
for(int i = 0; i < SZ(g[v]); i++){
int u = g[v][i].ff, w = g[v][i].ss;
if(u == p || vis[u]) continue;
map<int, int> mch;
dfs(u, v, w, 1, mch);
for(auto [value, x] : mch){
if(m.count(K - value)){
ans = min(ans, m[K - value] + x);
}
}
for(auto [value, x] : mch){
if(!m.count(value) || m[value] > x){
m[value] = x;
}
}
}
vis[v] = true;
for(auto [u, w] : g[v]){
if(u == p || vis[u])
continue;
ans = min(ans, solve(u, v, sz[u]));
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
:: K = K;
for(int i = 0; i < N - 1; i++){
int u = H[i][0], v = H[i][1];
g[u].pb({v, L[i]});
g[v].pb({u, L[i]});
}
int ans = solve(0, -1, N);
if(ans == INT_MAX){
ans = -1;
}
return ans;
}
