#include <bits/stdc++.h>
using namespace std;
// Pura Gente del Coach Moy y la Alexbriza
struct CentroidDecomposition {
int N, K;
vector<vector<pair<int, int>>> g;
vector<int> sz;
vector<bool> taken;
vector<int> minEdges;
int ans;
CentroidDecomposition(int N, int K) : N(N), K(K), g(N), sz(N), taken(N), minEdges(K + 1, N), ans(N) {}
void addEdge(int u, int v, int w) {
g[u].emplace_back(v, w), g[v].emplace_back(u, w);
}
int getSize(int u, int p) {
sz[u] = 1;
for (auto [v, _] : g[u]) {
if (v != p && !taken[v]) {
sz[u] += getSize(v, u);
}
}
return sz[u];
}
template <class F>
void traverse(int u, int p, int l, int d, F&& f) {
if (l > K) {
return;
}
f(l, d);
for (auto [v, w] : g[u]) {
if (v != p && !taken[v]) {
traverse(v, u, l + w, d + 1, f);
}
}
}
void decompose(int u, int globalSz) {
if (globalSz == -1) {
globalSz = getSize(u, -1);
}
for (auto [v, _] : g[u]) {
if (!taken[v] && 2 * sz[v] >= globalSz) {
sz[u] = 0;
decompose(v, globalSz);
return;
}
}
minEdges[0] = 0;
taken[u] = true;
for (auto [v, w] : g[u]) {
if (!taken[v]) {
traverse(v, u, w, 1, [&](int l, int d) { ans = min(ans, d + minEdges[K - l]); });
traverse(v, u, w, 1, [&](int l, int d) { minEdges[l] = min(minEdges[l], d); });
}
}
for (auto [v, w] : g[u]) {
if (!taken[v]) {
traverse(v, u, w, 1, [&](int l, int d) { minEdges[l] = N; });
}
}
for (auto [v, _] : g[u]) {
if (!taken[v]) {
decompose(v, -1);
}
}
}
int solve() {
if (!K) {
return 0;
}
decompose(0, -1);
return ans;
}
};
int best_path(int N, int K, int H[][2], int L[]) {
CentroidDecomposition cd(N, K);
for (int i = 0; i < N - 1; ++i) {
cd.addEdge(H[i][0], H[i][1], L[i]);
}
int ans = cd.solve();
return ans == N ? -1 : ans;
}
