#include "race.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define speedup cin.tie(0)->sync_with_stdio(0);
#define bitcount __builtin_popcount
#define all(x) begin(x), end(x)
#define pb push_back
#define vc vector
using ll = long long;
using pii = array<int, 2>;
mt19937 mt(chrono::steady_clock().now().time_since_epoch().count());
inline bool chmin(int &a, int b) {if (a > b) {a = b; return 1;} return 0;}
inline bool chmax(int &a, int b) {if (a < b) {a = b; return 1;} return 0;}
const int LG = 20, inf = 1e9;
int best_path(int n, int k, int ed[][2], int l[]) {
vc<vc<pii>> adj (n + 1);
for (int i = 0; i + 1 < n; i++) {
ed[i][0]++; ed[i][1]++;
adj[ed[i][0]].pb({ed[i][1], l[i]});
adj[ed[i][1]].pb({ed[i][0], l[i]});
}
if (k > 100) {
int cnt = 0;
vc<array<int, LG>> up (n + 1);
vc<int> d (n + 1), pf (n + 1), in (n + 1), out (n + 1);
auto dfs = [&](auto &&dfs, int u, int p) -> void {
d[u] = d[p] + 1;
in[u] = cnt++;
up[u][0] = p;
for (int k = 1; k < LG; k++)
up[u][k] = up[up[u][k - 1]][k - 1];
for (auto [v, w] : adj[u]) {
if (v == p) continue;
pf[v] = pf[u] + w;
dfs(dfs, v, u);
}
out[u] = cnt++;
}; dfs(dfs, 1, 1);
auto is = [&](int u, int v) -> bool {
return in[u] <= in[v] && out[v] <= out[u];
};
auto lca = [&](int u, int v) -> int {
if (is(u, v) || is(v, u)) return is(u, v)? u : v;
for (int k = LG - 1; k >= 0; k--)
if (!is(up[u][k], v)) u = up[u][k];
return up[u][0];
};
int ans = n + 1;
for (int u = 1; u <= n; u++) {
for (int v = 1; v <= n; v++) {
int p = lca(u, v);
int cost = d[u] + d[v] - 2 * d[p];
if (pf[u] + pf[v] - 2 * pf[p] == k) chmin(ans, cost);
}
}
if (ans == n + 1) return -1;
else return ans;
} else {
vc<vc<int>> dp (n + 1, vc<int> (k + 1, n + 1));
for (int i = 1; i <= n; i++) dp[i][0] = 0;
int ans = n + 1;
auto dfs = [&](auto &&dfs, int u, int p) -> void {
for (auto &[v, w] : adj[u]) {
if (v == p) continue;
else dfs (dfs, v, u);
for (int a = 0; a <= k; a++) {
if (dp[u][a] == n + 1) continue;
for (int b = 0; b + w <= k; b++) {
if (dp[v][b] == n + 1) continue;
if (a + b + w == k) chmin(ans, dp[u][a] + dp[v][b] + 1);
}
}
for(int b=0;b+w<=k;b++){
if(dp[v][b]>=inf) continue;
chmin(dp[u][b + w], dp[v][b] + 1);
}
}
}; dfs(dfs, 1, 1);
if (ans == n + 1) return -1;
return ans;
}
}
/*
4 3
0 1 1
1 2 2
1 3 4
2
*/
