#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int MAX = 200007, LIM = 1000007;
int Z[MAX], V[MAX], D[LIM];
vector<pii> G[MAX];
int GetSize(int cur, int prev) {
int& ret = Z[cur] = 1;
for (auto [next, _] : G[cur]) {
if (V[next] || next == prev) continue;
ret += GetSize(next, cur);
}
return ret;
}
int GetCent(int cur, int prev, int lim) {
for (auto [next, _] : G[cur]) {
if (V[next] || next == prev) continue;
if (Z[next] * 2 > lim) return GetCent(next, cur, lim);
}
return cur;
}
int ret;
vector<int> ST;
void DFS(int cur, int prev, int cnt, int cd, int K, bool upd) {
if (upd) ret = min(ret, cnt + D[K - cd]);
else {
D[cd] = min(D[cd], cnt);
ST.push_back(cd);
}
for (auto& [next, dist] : G[cur]) {
if (V[next] || next == prev) continue;
if (cd + dist <= K) DFS(next, cur, cnt + 1, cd + dist, K, upd);
}
}
void DnC(int cur, int K) {
int C = GetCent(cur, -1, GetSize(cur, -1));
V[C] = 1;
for (auto [next, dist] : G[C]) {
if (V[next] || dist > K) continue;
DFS(next, -1, 1, dist, K, 1);
DFS(next, -1, 1, dist, K, 0);
}
ret = min(ret, D[K]);
for (int n : ST) D[n] = 1e9;
ST.clear();
for (auto [next, _] : G[C]) if (!V[next]) DnC(next, K);
}
int best_path(int N, int K, int E[][2], int W[]) {
for (int i = 0; i < N - 1; ++i) {
int a = E[i][0] + 1, b = E[i][1] + 1;
G[a].emplace_back(b, W[i]);
G[b].emplace_back(a, W[i]);
}
ret = 1e9;
memset(D, 0x3f, sizeof(D));
DnC(1, K);
return (1E9 == ret ? -1 : ret);
}
