#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
const int N = 200000 + 7;
int n, k, best, sz[N], total;
ll dist[N];
bool vis[N];
vector<pair<int, int>> g[N];
void build(int a, int p = -1) {
sz[a] = 1;
for (auto &edge : g[a]) {
int b = edge.first, cost = edge.second;
if (b != p && !vis[b]) {
build(b, a);
sz[a] += sz[b];
}
}
}
int fcen(int a, int p = -1) {
int mx = total - sz[a];
for (auto &edge : g[a]) {
int b = edge.first, cost = edge.second;
if (b != p && !vis[b]) {
mx = max(mx, sz[b]);
}
}
if (mx <= total / 2) {
return a;
}
for (auto &edge : g[a]) {
int b = edge.first, cost = edge.second;
if (b != p && !vis[b] && mx == sz[b]) {
return fcen(b, a);
}
}
assert(0);
}
vector<pair<ll, int>> dists;
void dfs(int a, int p, int step) {
dists.push_back({dist[a], step});
for (auto &edge : g[a]) {
int b = edge.first, cost = edge.second;
if (b != p && !vis[b]) {
dist[b] = dist[a] + cost;
dfs(b, a, step + 1);
}
}
}
void solve(int a) {
build(a);
total = sz[a];
a = fcen(a);
vis[a] = 1;
map<ll, int> mn;
for (auto &edge : g[a]) {
int b = edge.first, cost = edge.second;
if (!vis[b]) {
dists.clear();
dist[b] = cost;
dfs(b, a, 1);
for (auto &val : dists) {
int other = k - val.first;
if (val.first == k) {
best = min(best, val.second);
}
if (mn.count(other)) {
best = min(best, mn[other] + val.second);
}
}
for (auto &val : dists) {
if (!mn.count(val.first)) {
mn[val.first] = val.second;
} else {
mn[val.first] = min(mn[val.first], val.second);
}
}
}
}
for (auto &edge : g[a]) {
int b = edge.first, cost = edge.second;
if (!vis[b]) {
solve(b);
}
}
}
int best_path(int nodes, int target, int edges[][2], int len_edges[]) {
best = N;
n = nodes;
k = target;
for (int i = 0; i < n; i++) {
vis[i] = 0;
g[i].clear();
}
for (int i = 0; i < n - 1; i++) {
g[edges[i][0]].push_back({edges[i][1], len_edges[i]});
g[edges[i][1]].push_back({edges[i][0], len_edges[i]});
}
solve(0);
if (best == N) {
best = -1;
}
return best;
}
