#include <bits/stdc++.h>
#include "race.h"
using ll = long long;
using pii = std::pair<int, int>;
std::vector < std::vector < pii > > g;
std::vector < ll > dist;
std::vector < int > depth;
void DFS1(int v, int p, ll sum, int d) {
dist[v] = sum;
depth[v] = d;
for (auto [u, w] : g[v])
if (u != p)
DFS1(u, v, sum + w, d + 1);
}
int len, ans = INT_MAX;
std::map < ll, int > DFS2(int v, int p) {
std::map < ll, int > dp;
dp[dist[v]] = depth[v];
for (auto [u, w] : g[v])
if (u != p) {
auto sub = DFS2(u, v);
if (sub.size() > dp.size())
std::swap(sub, dp);
for (auto [dist_, depth_] : sub)
if (dp.count(len + 2 * dist[v] - dist_)) {
ans = std::min(ans, dp[len + 2 * dist[v] - dist_] + depth_ - 2 * depth[v]);
}
for (auto [dist, depth] : sub)
if (!dp.count(dist))
dp[dist] = depth;
else
dp[dist] = std::min(dp[dist], depth);
}
return dp;
}
int best_path(int N, int K, int H[][2], int L[]) {
dist.resize(N);
depth.resize(N);
g.resize(N);
for (int i = 0; i < N - 1; i++) {
g[H[i][0]].push_back({ H[i][1], L[i] });
g[H[i][1]].push_back({ H[i][0], L[i] });
}
DFS1(0, 0, 0, 0);
len = K;
DFS2(0, 0);
return ans == INT_MAX ? -1 : ans;
}
// int main() {
// int n, k; std::cin >> n >> k;
// int h[n][2], l[n];
// for (int i = 0; i < n - 1; i++)
// std::cin >> h[i][0] >> h[i][1] >> l[i];
// std::cout << best_path(n, k, h, l) << "\n";
// }
