#include <bits/stdc++.h>
void steroids(const std::string &s = "", const std::string &file_in = ".in", const std::string &file_out = ".out") {
std::cin.tie(0) -> sync_with_stdio(0);
if (!s.empty()) {
freopen((s + file_in).c_str(), "r", stdin);
freopen((s + file_out).c_str(), "w", stdout);
}
}
const int N = 2e5;
std::vector<std::pair<int, int>> adj[N];
int sub_sz[N];
bool del[N];
int n, k, ans;
std::map<int, int> current;
std::vector<std::pair<int, int>> to_be_merged;
int dfs_sz(const int &u, const int &p) {
sub_sz[u] = 1;
for (const auto &[v, _] : adj[u]) {
if (v == p || del[v]) continue;
sub_sz[u] += dfs_sz(v, u);
}
return sub_sz[u];
}
int get_centroid(const int &u, const int &p, const int &sz) {
for (const auto &[v, _] : adj[u]) {
if (v == p || del[v]) continue;
if (sub_sz[v] * 2 > sz) return get_centroid(v, u, sz);
}
return u;
}
void get_dist_to_centroid(const int &u, const int &p, const int &d, const int &l) {
if (d > k) return;
to_be_merged.push_back({d, l});
for (const auto &[v, w] : adj[u]) {
if (v == p || del[v]) continue;
get_dist_to_centroid(v, u, d+w, l+1);
}
}
void ctd(const int &u) {
int centroid = get_centroid(u, -1, dfs_sz(u, -1));
del[centroid] = true;
current.clear();
to_be_merged.clear();
for (const auto &[child, dist] : adj[centroid]) {
if (del[child]) continue;
get_dist_to_centroid(child, centroid, dist, 1);
for (const auto &[d, l] : to_be_merged) {
if (current.find(k - d) != current.end()) ans = std::min(ans, current[k-d] + l);
else if (d == k) ans = std::min(ans, l);
}
for (const auto &[d, l] : to_be_merged) {
if (current.count(d)) current[d] = std::min(current[d], l);
else current[d] = l;
}
to_be_merged.clear();
}
for (const auto &[nxt, _] : adj[centroid]) {
if (!del[nxt]) ctd(nxt);
}
}
int best_path(int nn, int kk, int h[][2], int l[]) {
n = nn;
k = kk;
ans = n;
for (int i = 0; i < n; i++) {
int u = h[i][0], v = h[i][1], w = l[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
ctd(0);
return (ans == n ? -1 : ans);
}
