#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using lli = long long;
const int MAXN = 1e5 + 10;
const int MAXK = 1e6 + 10;
vector<pair<int, int>> graph[MAXN];
vector<int> subs[MAXN];
int sub[MAXN], dist[MAXK], aprof[MAXN];
bool marc[MAXN];
lli prof[MAXN];
void dfs_sub(int u, int p) {
sub[u] = 1;
for (auto [v, c]: graph[u]) {
if (v == p) continue;
dfs_sub(v, u);
sub[u] += sub[v];
}
}
void dfs_prof(int u, int p, int cor) {
subs[cor].push_back(u);
for (auto [v, c]: graph[u]) {
if (marc[v] || v == p) continue;
prof[v] = prof[u] + c;
aprof[v] = aprof[u] + 1;
dfs_prof(v, u, cor);
}
}
int dfs_cent(int u, int p, int n) {
for (auto [v, c]: graph[u]) {
if (v == p) continue;
if (sub[v] >= n/2) return dfs_cent(v, u, n);
}
return u;
}
int dfs(int u, int p, int n, int k) {
dfs_sub(u, p);
int c = dfs_cent(u, p, n);
marc[c] = true;
for (int i = 0; i < graph[c].size(); ++i) {
auto [v, cost] = graph[c][i];
if (!marc[v]) {
prof[v] = cost;
aprof[v] = 1;
dfs_prof(v, c, i);
}
}
int ans = 1e9;
dist[0] = 0;
for (int i = 0; i < graph[c].size(); ++i) {
for (int v: subs[i])
if (prof[v] <= k)
ans = min(ans, dist[k - prof[v]] + aprof[v]);
for (int v: subs[i])
if (prof[v] < MAXK) dist[prof[v]] = min(dist[prof[v]], aprof[v]);
}
for (int i = 0; i < graph[c].size(); ++i) {
for (int v: subs[i])
dist[v] = 1e9;
subs[i].clear();
}
for (auto [v, cost]: graph[u])
if (!marc[v]) ans = min(ans, dfs(v, c, n, k));
return ans;
}
int best_path(int n, int k, int edges[][2], int costs[]) {
for (int i = 0; i < n-1; ++i) {
graph[edges[i][0]].emplace_back(edges[i][1], costs[i]);
graph[edges[i][1]].emplace_back(edges[i][0], costs[i]);
}
for (int i = 0; i < MAXK; ++i)
dist[i] = 1e9;
int ans = dfs(1, 1, n, k);
if (ans == 1e9) return -1;
return ans;
}
