#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int MAXK = 1000005;
const int INF = 1e9;
struct Edge {
int to, w;
};
vector<Edge> adj[MAXN];
bool vis[MAXN];
int sz[MAXN];
int min_edges[MAXK];
int ans, target_k;
vector<int> q;
int get_sz(int u, int p) {
sz[u] = 1;
for (auto &e : adj[u]) {
if (e.to != p && !vis[e.to]) {
sz[u] += get_sz(e.to, u);
}
}
return sz[u];
}
int get_centroid(int u, int p, int total) {
for (auto &e : adj[u]) {
if (e.to != p && !vis[e.to] && sz[e.to] > total / 2) {
return get_centroid(e.to, u, total);
}
}
return u;
}
void get_paths(int u, int p, int depth, int weight, vector<pair<int, int>> &paths) {
if (weight > target_k) return;
paths.push_back({weight, depth});
for (auto &e : adj[u]) {
if (e.to != p && !vis[e.to]) {
get_paths(e.to, u, depth + 1, weight + e.w, paths);
}
}
}
void decompose(int u) {
int centroid = get_centroid(u, -1, get_sz(u, -1));
vis[centroid] = true;
q.clear();
min_edges[0] = 0;
q.push_back(0);
for (auto &e : adj[centroid]) {
if (!vis[e.to]) {
vector<pair<int, int>> subtree_paths;
get_paths(e.to, centroid, 1, e.w, subtree_paths);
for (auto &path : subtree_paths) {
int rem = target_k - path.first;
if (rem >= 0) {
ans = min(ans, path.second + min_edges[rem]);
}
}
for (auto &path : subtree_paths) {
if (min_edges[path.first] == INF) {
q.push_back(path.first);
}
min_edges[path.first] = min(min_edges[path.first], path.second);
}
}
}
for (int weight : q) min_edges[weight] = INF;
for (auto &e : adj[centroid]) {
if (!vis[e.to]) decompose(e.to);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
target_k = K;
ans = INF;
for (int i = 0; i < N; i++) {
adj[i].clear();
vis[i] = false;
}
for (int i = 0; i <= K; i++) min_edges[i] = INF;
for (int i = 0; i < N - 1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
decompose(0);
return (ans >= INF) ? -1 : ans;
}
