#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3;
int n, k;
vector<pair<int, int>> g[N];
bool vst[N];
int sz[N], min_edge[5 * N], ans = N;
vector<int> tmp;
int get_sz(int u, int p) {
sz[u] = 1;
for (auto [v, w]: g[u]) if (v != p && !vst[v])
sz[u] += get_sz(v, u);
return sz[u];
}
int centroid(int u, int p, int csz) {
for (auto [v, w]: g[u]) if (v != p && !vst[v]) {
if (sz[v] > csz / 2) return centroid(v, u, csz);
}
return u;
}
void dfs(int u, int p, int cur_len, int cnt, bool get_ans) {
if (cur_len > k) return;
if (get_ans) ans = min(ans, cnt + min_edge[k - cur_len]);
else {
tmp.push_back(cur_len);
min_edge[cur_len] = min(min_edge[cur_len], cnt);
}
for (auto [v, w]: g[u]) if (v != p && !vst[v])
dfs(v, u, cur_len + w, cnt + 1, get_ans);
}
void build_cd(int u) {
u = centroid(u, 0, get_sz(u, 0));
vst[u] = true;
for (auto [v, w]: g[u]) if (!vst[v]) {
dfs(v, u, w, 1, 1);
dfs(v, u, w, 1, 0);
}
ans = min(ans, min_edge[k]);
while (!tmp.empty()) {
min_edge[tmp.back()] = N;
tmp.pop_back();
}
for (auto [v, w]: g[u]) if (!vst[v])
build_cd(v);
}
int solve() {
for (int i = 0; i < 5 * N; ++i)
min_edge[i] = N;
build_cd(1);
return (ans != N ? ans : -1);
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
for (int i = 0; i < N - 1; ++i) {
g[H[i][0] + 1].emplace_back(H[i][1] + 1, L[i]);
g[H[i][1] + 1].emplace_back(H[i][0] + 1, L[i]);
}
return solve();
}
