#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define inp(name) freopen(name, "r", stdin);
#define out(name) freopen(name, "w", stdout);
const int N = 2e5 + 5;
int n, k;
int s[N], vst[N], mn[5 * N], tin[5 * N];
vector <pii> adj[N];
int timer = 0;
void pre_dfs (int u, int v){
s[u] = 1;
for (auto [i, w] : adj[u]){
if (vst[i] || i == v) continue;
pre_dfs(i, u);
s[u] += s[i];
}
}
int centroid (int u, int v, int n){
for (auto [i, w] : adj[u]){
if (vst[i] || i == v) continue;
if (s[i] <= n/2) continue;
return centroid(i, u, n);
}
return u;
}
int ans = INT_MAX;
void add(int u, int v, int len, int dist){
if (dist <= k && tin[k - dist] == timer){
ans = min(ans, len + mn[k - dist]);
}
for (auto [i, w] : adj[u]){
if (i == v || vst[i]) continue;
add(i, u, len + 1, dist + w);
}
}
void dfs_dist(int u, int v, int len, int dist){
if (dist <= k){
if (tin[dist] != timer){
mn[dist] = len;
tin[dist] = timer;
}
else mn[dist] = min(mn[dist], len);
}
for (auto [i, w] : adj[u]){
if (i == v || vst[i]) continue;
dfs_dist(i, u, len + 1, dist + w);
}
}
void dnc(int u){
pre_dfs(u, 0);
int c = centroid(u, 0, s[u]);
tin[0] = ++timer;
for (auto [i, w] : adj[c]){
if (vst[i]) continue;
add(i, c, 1, w);
dfs_dist(i, c, 1, w);
}
vst[c] = 1;
for (auto [i, w] : adj[c]){
if (vst[i]) continue;
dnc(i);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
for (int i = 1; i < n; i ++){
int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
fill (mn + 1, mn + k + 5, 1e9);
dnc(1);
if (ans > 1e9) ans = -1;
return ans;
}
