#include "race.h"
#include <bits/stdc++.h>
template<typename T>
using vec = std::vector<T>;
using namespace std;
struct G {
private:
void dfs(int u) {
for (auto [c, w] : adj[u]) if (c != bin[u][0]) {
depth[c] = depth[u] + 1;
uptow[c] = uptow[u] + w;
bin[c][0] = u;
dfs(c);
}
}
public:
int size;
vec<vec<array<int, 2>>> adj;
vec<array<int, 20>> bin;
vec<int> depth;
vec<int> uptow;
G(int n) : size(n), adj(n), bin(n), depth(n), uptow(n) {}
void undirectedAdd(int i, int j, int w) {
adj[i].push_back({j, w});
adj[j].push_back({i, w});
}
void prep() {
for (int i = 0; i < size; i++) fill(bin[i].begin(), bin[i].end(), -1);
dfs(0);
for (int k = 1; k < 20; k++) for (int i = 0; i < size; i++) if (bin[i][k - 1] != -1)
bin[i][k] = bin[bin[i][k - 1]][k - 1];
}
void raise(int &u, int k) {
if (k == 0) return;
assert(k <= depth[u]);
for (int i = 19; 0 <= i; i--) if ((k>>i)&1)
u = bin[u][i];
}
int lcm(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
int diff = depth[v] - depth[u];
raise(v, diff);
if (u == v) return u;
for (int i = 19; 0 <= i; i--) {
set s{bin[u][i], bin[v][i]};
if (s.size() == 2 && *s.begin() != -1) {
u = bin[u][i];
v = bin[v][i];
}
}
assert(bin[u][0] == bin[v][0]);
return bin[u][0];
}
array<int, 2> dist(int u, int v) {
int l = lcm(u, v);
return {
depth[u] + depth[v] - 2 * depth[l],
uptow[u] + uptow[v] - 2 * uptow[l]
};
}
};
int best_path(int N, int K, int H[][2], int L[]) {
G g(N);
for (int i = 0; i < N - 1; i++)
g.undirectedAdd(H[i][0], H[i][1], L[i]);
g.prep();
optional<int> ans;
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++) {
auto [dist, distw] = g.dist(i, j);
if (distw == K)
ans = min(ans.value_or(INT32_MAX), dist);
}
return ans.value_or(-1);
}
