#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
int best_path(int N, int K, int H[][2], int L[]) {
int n = N;
int k = K;
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n - 1; ++i) {
int x = H[i][0];
int y = H[i][1];
int z = L[i];
g[x].emplace_back(y, z);
g[y].emplace_back(x, z);
}
vector<bool> removed(n, false);
vector<int> sz(n);
auto GetCenter = [&](int r) {
vector<int> pv(n);
auto DFS = [&](auto&& self, int v) -> void {
sz[v] = 1;
for (auto [u, _] : g[v]) {
if (u != pv[v] && !removed[u]) {
pv[u] = v;
self(self, u);
sz[v] += sz[u];
}
}
};
pv[r] = -1;
DFS(DFS, r);
int tot = sz[r];
while (true) {
int nr = -1;
for (auto [u, _] : g[r]) {
if (u != pv[r] && !removed[u] && sz[u] * 2 > tot) {
nr = u;
break;
}
}
if (nr == -1) {
return r;
}
r = nr;
}
};
int ans = n;
int iter = 0;
vector<int> aux(k + 1, 0);
vector<int> dp(k + 1, 0);
auto Find = [&](auto&& self, int v, int pv, int dist, int depth) -> void {
if (dist > k) {
return;
}
if (aux[k - dist] == iter) {
ans = min(ans, dp[k - dist] + depth);
}
if (dist == k) {
ans = min(ans, depth);
}
for (auto [u, w] : g[v]) {
if (!removed[u] && u != pv) {
self(self, u, v, dist + w, depth + 1);
}
}
};
auto Calc = [&](auto&& self, int v, int pv, int dist, int depth) -> void {
if (dist > k) {
return;
}
if (aux[dist] < iter) {
aux[dist] = iter;
dp[dist] = depth;
} else
if (dp[dist] > depth) {
aux[dist] = iter;
dp[dist] = depth;
}
for (auto [u, w] : g[v]) {
if (!removed[u] && u != pv) {
self(self, u, v, dist + w, depth + 1);
}
}
};
auto Solve = [&](auto&& self, int v) -> void {
v = GetCenter(v);
if (sz[v] == 1) {
return;
}
iter += 1;
for (auto [u, w] : g[v]) {
if (!removed[u]) {
Find(Find, u, v, w, 1);
Calc(Calc, u, v, w, 1);
}
}
removed[v] = true;
for (auto [u, _] : g[v]) {
if (!removed[u]) {
self(self, u);
}
}
};
Solve(Solve, 0);
return (ans == n ? -1 : ans);
}
