#include "race.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e5+5;
vector<pair<int, int>> adj[N];
int sz[N]; bool bl[N];
int ans = 1e9, k;
int dfs(int cur, int par) {
sz[cur] = 1;
for (auto p : adj[cur]) {
int u = p.first, w = p.second;
if (!bl[u] && u != par)
sz[cur] += dfs(u, cur);
}
return sz[cur];
}
int cent(int cur, int par, int tsz) {
for (auto p : adj[cur]) if (p.first != par && !bl[p.first] &&
tsz/2 < sz[p.first]) return cent(p.first, cur, tsz);
return cur;
}
void dfs2(int cur, int par, int d, int nm, unordered_map<int, int>& aux) {
if (aux.find(d) == aux.end()) {
aux[d] = nm;
} else {
aux[d] = min(aux[d], nm);
}
for (auto p : adj[cur]) {
int u = p.first, w = p.second;
if (u != par && !bl[u]) {
dfs2(u, cur, d + w, nm+1, aux);
}
}
}
void solve(int cur = 0) {
int c = cent(cur, cur, dfs(cur, cur));
bl[c] = true;
unordered_map<int, int> cnt;
cnt[0] = 0;
for (auto p : adj[c]) {
int u = p.first, w = p.second;
if (!bl[u]) {
unordered_map<int, int> aux;
dfs2(u, c, w, 1, aux);
for (auto x : aux) {
if (cnt.find(k - x.first) != cnt.end())
ans = min(ans, x.second + cnt[k - x.first]);
}
for (auto x : aux) {
if (cnt.find(x.first) != cnt.end())
cnt[x.first] = min(cnt[x.first], x.second);
else cnt[x.first] = x.second;
}
}
}
for (auto p : adj[c]) if (!bl[p.first]) solve(p.first);
}
int best_path(int N, int K, int H[][2], int L[])
{
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();
return (ans >= 1e9 ? -1 : ans);
}
