#include <iostream>
#include <utility>
#include <vector>
#include <tuple>
#include <map>
#include "race.h"
using namespace std;
const int maxn = 200005;
const int inf = 1000000000;
int H[maxn][2];
int L[maxn];
int n;
long long k;
vector<pair<int, int>> g[maxn];
long long pathToRoot[maxn];
int depth[maxn];
map<long long, int> info[maxn];
void dfs_precompute(int node, int parent, long long currPath, int currDepth) {
pathToRoot[node] = currPath;
depth[node] = currDepth;
info[node][currPath] = currDepth;
for (auto [v, w] : g[node]) {
if (v == parent) continue;
dfs_precompute(v, node, currPath + w, currDepth + 1);
}
}
int ans = inf;
void dfs_small_to_large(int node, int parent) {
long long target = k + 2 * pathToRoot[node];
for (auto [v, w] : g[node]) {
if (v == parent) continue;
dfs_small_to_large(v, node);
if (info[node].size() < info[v].size()) {
swap(info[node], info[v]);
}
for (auto [dist, edges] : info[v]) {
if (info[node].find(target - dist) != info[node].end()) {
ans = min(ans, info[node][target - dist] + edges - 2 * depth[node]);
}
}
for (auto [dist, edges] : info[v]) {
if (info[node].find(dist) == info[node].end()) {
info[node].insert({dist, edges});
} else {
info[node][dist] = min(info[node][dist], edges);
}
}
}
}
int best_path(int A, int B, int edges[][2], int weights[]) {
n = A;
k = B;
for (int i = 0; i < n; ++i) {
int u = edges[i][0];
int v = edges[i][1];
int w = weights[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs_precompute(0, -1, 0, 0);
dfs_small_to_large(0, -1);
if (ans == inf) return -1;
return ans;
}
