#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
int sub[200000], K;
bool ct[200000];
vector<pll> adj[200000], vec;
ll dist[200000], mn[1000001], ans;
vector<int> rm;
int dfs(int u, int p) {
sub[u] = 1;
for (auto [v, w]: adj[u]) if (v != p && !ct[v]) sub[u] += dfs(v, u);
return sub[u];
}
int dfs(int u, int p, int n) {
for (auto [v, w]: adj[u]) if (v != p && !ct[v] && sub[v] > n/2) return dfs(v, u, n);
return u;
}
void populate_dist(int u, int p, int d) {
if (dist[u] <= K) vec.push_back({d, dist[u]});
for (auto [v, w]: adj[u]) if (v != p && !ct[v]) dist[v] = dist[u] + w, populate_dist(v, u, d+1);
}
void build(int u, int p) {
int n = dfs(u, p);
int centroid = dfs(u, p, n);
ct[centroid] = 1;
// cout << centroid << '\n';
for (auto [v, w]: adj[centroid]) if (!ct[v]) {
dist[v] = w; populate_dist(v, centroid, 1);
// for (auto [de, di]: vec) cout << de << ' ' << di << '\n';
for (auto [de, di]: vec) ans = min(ans, mn[K-di]+de);
for (auto [de, di]: vec) mn[di] = min(mn[di], de), rm.push_back(di);
vec.clear();
}
for (auto e: rm) mn[e] = 0x3f3f3f3f;
rm.clear();
for (auto [v, w]: adj[centroid]) if (!ct[v]) build(v, centroid);
}
int best_path(int n, int k, int h[][2], int l[]) {
K = k;
ans = 0x3f3f3f3f;
for (int i = 0; i < n-1; i++) {
adj[h[i][0]].emplace_back(h[i][1], l[i]);
adj[h[i][1]].emplace_back(h[i][0], l[i]);
}
memset(mn, 0x3f, sizeof mn); mn[0] = 0;
build(0, -1);
return ans <= 200000 ? ans : -1;
}
