#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;
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]});
}
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;
}
/*
4 3
0 1 1
1 2 2
1 3 4
2
*/
