#include <bits/stdc++.h>
#include "race.h"
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vii = vector<pii>;
using vll = vector<pll>;
static const int INF = 0x3f3f3f3f;
static const int maxn = 200005;
static const int maxk = 1000005;
static int n, k;
static array<int, maxn> sz;
static array<int, maxk> mn;
static array<vii, maxn> adj;
static bitset<maxn> removed;
static void build_size(int u, int p) {
sz[u] = 1;
for (auto &[v, w]: adj[u]) {
if (v == p || removed[v]) continue;
build_size(v, u);
sz[u] += sz[v];
}
}
static int find_centroid(int u, int p, int tree_size) {
for (auto &[v, w]: adj[u]) {
if (v == p || removed[v]) continue;
if (sz[v] > tree_size / 2) return find_centroid(v, u, tree_size);
}
return u;
}
static int dfs_get(int u, int p, int dep, int dis) {
if (dis > k) return INF;
int ans = min(dep + mn[k - dis], INF);
for (auto &[v, w]: adj[u]) {
if (v == p || removed[v]) continue;
ans = min(ans, dfs_get(v, u, dep + 1, dis + w));
}
return ans;
}
static void dfs_upd(int u, int p, int dep, int dis, vi& used) {
if (dis > k) return;
mn[dis] = min(mn[dis], dep);
used.push_back(dis);
for (auto &[v, w]: adj[u]) {
if (v == p || removed[v]) continue;
dfs_upd(v, u, dep + 1, dis + w, used);
}
}
static int centroid_decomposition(int root) {
build_size(root, -1);
int centroid = find_centroid(root, -1, sz[root]);
int ans = INF;
vi used;
for (auto &[v, w]: adj[centroid]) {
if (removed[v]) continue;
ans = min(ans, dfs_get(v, centroid, 1, w));
dfs_upd(v, centroid, 1, w, used);
}
for (int x: used) if (x > 0) mn[x] = INF;
removed[centroid] = 1;
for (auto& [v, w]: adj[centroid]) {
if (removed[v]) continue;
ans = min(ans, centroid_decomposition(v));
}
return ans;
}
int best_path(int _n, int _k, int edges[][2], int W[]) {
n = _n, k = _k;
for (int i = 0; i < n - 1; i++) {
int u = edges[i][0], v = edges[i][1];
adj[u].push_back({v, W[i]});
adj[v].push_back({u, W[i]});
}
for (int i = 1; i <= k; i++) {
mn[i] = INF;
}
int ans = centroid_decomposition(0);
if (ans >= INF) ans = -1;
return ans;
}
