#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int N = 200000 + 7;
const int K = 1000000 + 7;
int last[K], mn[K], event;
int n, k, best, sz[N], total, dist[N];
bool vis[N];
vector<pair<int, int>> g[N];
int get_mn(int x) {
if (last[x] != event) return N;
return mn[x];
}
void upd(int x, int val) {
if (last[x] != event) {
last[x] = event;
mn[x] = val;
} else {
mn[x] = min(mn[x], val);
}
}
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);
}
}
}
vector<pair<int, int>> dists;
void dfs(int a, int p, int step) {
if (dist[a] > k) {
return;
}
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;
event++;
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);
}
best = min(best, get_mn(other) + val.second);
}
for (auto &val : dists) {
upd(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;
}
