#include "bits/stdc++.h"
using namespace std;
#define ll long long
struct centroid {
int n, k;
vector<vector<pair<int, int>>> adj;
vector<int> siz, is_removed;
map<ll, int> mp;
int ans = n + 1;
centroid(int n, int k, vector<vector<pair<int, int>>> adj) : n(n), k(k), adj(adj), siz(n + 1), is_removed(n + 1) {
decomp(0);
if (ans == n + 1)
ans = -1;
}
void dfs_size(int i, int p) {
siz[i] = 1;
for (auto &[it, d]: adj[i])
if (it != p and !is_removed[it]) {
dfs_size(it, i);
siz[i] += siz[it];
}
}
int get_centroid(int i, int p, int tot) {
for (auto &[it, d]: adj[i])
if (it != p and !is_removed[it])
if (siz[it] * 2 > tot)
return get_centroid(it, i, tot);
return i;
}
void get_ans(int i, int p, ll dist, int d) {
if (dist > k)return;
if (mp.count(k - dist))
ans = min(ans, mp[k - dist] + d);
for (auto &[it, c]: adj[i])
if (it != p and !is_removed[it])
get_ans(it, i, dist + c, d + 1);
}
void dfs(int i, int p, ll dist, int d) {
if (dist > k)return;
if (!mp.count(dist))
mp[dist] = d;
else
mp[dist] = min(mp[dist], d);
for (auto &[it, c]: adj[i])
if (it != p and !is_removed[it])
dfs(it, i, dist + c, d + 1);
}
void decomp(int i) {
dfs_size(i, i);
int cent = get_centroid(i, i, siz[i]);
mp[0] = 0;
for (auto &[it, c]: adj[cent])
if (!is_removed[it]) {
get_ans(it, cent, c, 1);
dfs(it, cent, c, 1);
}
mp.clear();
is_removed[cent] = 1;
for (auto &[it, d]: adj[cent])
if (!is_removed[it])
decomp(it);
}
};
int best_path(int N, int K, int H[][2], int L[]) {
int n = N;
int k = K;
vector<vector<pair<int, int>>> adj(n + 1);
for (int g = 0; g < n - 1; g++) {
int a = H[g][0], b = H[g][1], c = L[g];
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
centroid cn(n, k, adj);
return cn.ans;
}
