#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 1e6 + 5;
map<int64_t, int> sub[MXN];
int lvl[MXN], ans = INT_MAX;
vector<array<int64_t, 2>> adj[MXN];
void dfs(const int &node, int64_t sum, const int &k, int par = 0) {
sub[node][sum] = lvl[node];
for (auto &[child, cost]: adj[node])
if (child != par) {
lvl[child] = lvl[node] + 1;
dfs(child, sum + cost, k, node);
if ((int)sub[node].size() < (int)sub[child].size()) swap(sub[node], sub[child]);
int64_t target;
for (auto &[val, level] : sub[child]) {
target = k - val + (sum << 1);
if (sub[node].count(target)) ans = min(ans, sub[node][target] + level - (lvl[node] << 1));
if (sub[node].count(val)) sub[node][val] = min(sub[node][val], level);
else sub[node][val] = level;
}
target = sum + k;
if (sub[node].count(target)) ans = min(ans, sub[node][target] - lvl[node]);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N; i++)
adj[H[i][0]].push_back({H[i][1], L[i]}), adj[H[i][1]].push_back({H[i][0], L[i]});
dfs(0, 0, K);
return (ans == INT_MAX ? -1 : ans);
}
/*
testcase1:
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
testcase2:
4 3
0 1 1
1 2 2
1 3 4
2
testcase3:
3 3
0 1 1
1 2 1
-1
*/
