#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
const int MAXN = 2e5;
const ll INF = 1e18;
vector <pii> adj[MAXN + 5];
ll ans = INF, N, K, vis[MAXN + 5], sz[MAXN + 5];
void dfs(ll idx, ll par) {
sz[idx] = 1;
for (auto [i, j] : adj[idx]) {
if (i != par && !vis[i]) {
dfs(i, idx);
sz[idx] += sz[i];
}
}
}
ll find_centroid(ll idx, ll par, ll cur_sz) {
for (auto [i, j] : adj[idx]) {
if (i != par && !vis[i]) {
if (sz[i] > cur_sz / 2) return find_centroid(i, idx, cur_sz);
}
}
return idx;
}
vector <ll> v;
ll dist[MAXN + 5], dist2[MAXN + 5];
map<ll, ll> mp;
void dfs2(ll idx, ll par) {
v.push_back(idx);
for (auto [i, j] : adj[idx]) {
if (i != par && !vis[i]) {
dist[i] = dist[idx] + j;
dist2[i] = dist2[idx] + 1;
dfs2(i, idx);
}
}
}
void solve(ll idx) {
dfs(idx, -1);
ll cen = find_centroid(idx, -1, sz[idx]);
vis[cen] = 1;
dist[cen] = dist2[cen] = 0;
for (auto [i, j] : adj[cen]) {
if (!vis[i]) {
dist[i] = dist[cen] + j;
dist2[i] = dist2[cen] + 1;
v.clear();
dfs2(i, cen);
for (auto x : v) {
if (mp.count(K - dist[x])) {
ans = min(ans, dist2[x] + mp[K - dist[x]]);
}
}
for (auto x : v) {
if (!mp.count(dist[x])) mp[dist[x]] = dist2[x];
else mp[dist[x]] = min(mp[dist[x]], dist2[x]);
}
}
}
if (mp.count(K)) {
ans = min(ans, mp[K]);
}
mp.clear();
for (auto [i, j] : adj[cen]) {
if (!vis[i]) solve(i);
}
}
int best_path(int n, int k, int H[][2], int L[]) {
N = n, K = k;
for (int i = 0; i < N - 1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
solve(0);
if (ans == INF) ans = -1;
return ans;
}
