#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
const int NN = 2e5 + 5;
vector<vector<pair<int, int>>> G;
bool used[NN];
int sz[NN];
int compSize;
int k;
int answ;
unordered_map<int, int> depth, cur_depth;
void dfs(int node, int parent) {
sz[node] = 1;
for (auto& [to, w] : G[node]) {
if (to != parent && !used[to]) {
dfs(to, node);
sz[node] += sz[to];
}
}
}
int find_centroid(int node, int parent) {
for (auto& [to, w] : G[node]) {
if (to != parent && !used[to] && sz[to] * 2 > compSize) {
return find_centroid(to, node);
}
}
return node;
}
int get_centroid(int u) {
dfs(u, -1);
compSize = sz[u];
return find_centroid(u, -1);
}
void collect_paths(int node, int parent, int depth_now, int sum_now, vector<pair<int, int>>& paths) {
if (sum_now > k) return;
paths.emplace_back(sum_now, depth_now);
for (auto& [to, w] : G[node]) {
if (to != parent && !used[to]) {
collect_paths(to, node, depth_now + 1, sum_now + w, paths);
}
}
}
void process(int centroid) {
depth.clear();
depth[0] = 0; // Distance 0 at depth 0
for (auto& [to, w] : G[centroid]) {
if (used[to]) continue;
vector<pair<int, int>> paths;
collect_paths(to, centroid, 1, w, paths);
for (auto& [sum, d] : paths) {
if (depth.count(k - sum)) {
answ = min(answ, d + depth[k - sum]);
}
}
for (auto& [sum, d] : paths) {
if (!depth.count(sum)) depth[sum] = d;
else depth[sum] = min(depth[sum], d);
}
}
}
void decompose(int u) {
int c = get_centroid(u);
used[c] = true;
process(c);
for (auto& [to, w] : G[c]) {
if (!used[to]) {
decompose(to);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
// Reset globals
G.clear();
G.resize(N);
memset(used, 0, sizeof(used));
answ = INF;
k = K;
for (int i = 0; i < N - 1; ++i) {
int u = H[i][0], v = H[i][1], w = L[i];
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
decompose(0);
return (answ == INF ? -1 : answ);
}
