#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<pair<int, int>>> tree;
vector<int> sub;
vector<bool> del;
int n, k;
int ans = -1;
map<ll, int> cnt;
void calc_subs(int node, int par) {
sub[node] = 1;
for (auto [next, w]: tree[node]) {
if (del[next] || next == par) continue;
calc_subs(next, node);
sub[node] += sub[next];
}
}
int find_centroid(int node, int tot, int par = 0) {
for (auto [next, w]: tree[node]) {
if (del[next] || next == par) continue;
if (sub[next] * 2 >= tot) return find_centroid(next, tot, node);
}
return node;
}
void add(int node, int par, ll totLen, int dep = 1) {
if (!cnt[totLen]) {
cnt[totLen] = dep;
}
else cnt[totLen] = min(cnt[totLen], dep);
for (auto [next, w]: tree[node]) {
if (next == par || del[next]) continue;
add(next, node, totLen + w, dep+1);
}
}
void find_ans(int node, int par, ll totLen, int dep = 1) {
ll need = k - totLen;
if (need == 0) {
if (ans == -1) ans = dep;
else ans = min(ans, dep);
}
if (need > 0 && cnt[need]) {
if (ans == -1) ans = cnt[need] + dep;
else ans = min(ans, cnt[need] + dep);
}
for (auto [next, w]: tree[node]) {
if (next == par || del[next]) continue;
find_ans(next, node, totLen + w, dep+1);
}
}
void build(int node) {
calc_subs(node, 0);
int cd = find_centroid(node, sub[node]);
cnt.clear();
for (auto [next, w]: tree[cd]) {
if (del[next]) continue;
find_ans(next, cd, w);
add(next, cd, w);
}
cnt.clear();
del[cd] = true;
for (auto [next, w]: tree[cd]) {
if (del[next]) continue;
build(next);
}
}
int best_path(int N, int K, vector<vector<int>> H, vector<int> L) {
n = N;
k = K;
tree.resize(n+1);
del.assign(n+1, false);
sub.assign(n+1, 0);
for (int i = 0; i < n-1; i++) {
H[i][0]++;
H[i][1]++;
tree[H[i][0]].push_back({H[i][1], L[i]});
tree[H[i][1]].push_back({H[i][0], L[i]});
}
build(1);
if (ans != -1) ans++;
return ans;
}
/*
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << best_path(3, 3, {{0, 1}, {0, 2}, {}}) << "\n";
}*/
