#include <bits/stdc++.h>
using namespace std;
const int nax = 2e5 + 5;
vector<pair<int, int>> edges[nax];
int sz[nax];
bool dead[nax];
int cent (int u, int p, int comp) {
for (auto v : edges[u]) {
if (p != v.first && !dead[v.first] && sz[v.first] * 2 > comp) {
return cent (v.first, u, comp);
}
}
return u;
}
void dfs (int u, int p) {
sz[u] = 1;
for (auto v : edges[u]) {
if (v.first != p && !dead[v.first]) {
dfs (v.first, u);
sz[u] += sz[v.first];
}
}
}
map<long long, int> mp;
void dfs2 (int u, int p, long long x, int depth) {
if (mp[x] == 0 && x != 0) {
mp[x] = depth;
}
mp[x] = min(mp[x], depth);
for (auto v : edges[u]) {
if (v.first != p && !dead[v.first]) {
dfs2 (v.first, u, x + v.second, depth + 1);
}
}
}
int ans = 1e9;
int K;
void dfs3 (int u, int p, long long x, int depth) {
if ((K - x > 0 && mp[K - x] > 0) || (K - x == 0))
ans = min(ans, depth + mp[K - x]);
cout << mp[K - x] << ' ' << x << '\n';
for (auto v : edges[u]) {
if (v.first != p && !dead[v.first]) {
dfs3 (v.first, u, x + v.second, depth + 1);
}
}
}
void decomp (int u) {
dfs (u, - 1);
int C = cent(u, -1, sz[u]);
for (auto v : edges[C]) {
if (!dead[v.first]) {
dfs3(v.first, C, v.second, 1);
dfs2 (v.first, C, v.second, 1);
}
}
dead[C] = 1;
mp.clear();
for (auto v : edges[C]) {
if (!dead[v.first])
decomp (v.first);
}
}
int best_path(int n, int k, int H[][2], int l[]) {
K = k;
for (int i = 0; i < n - 1; ++i) {
int u = H[i][0];
int v = H[i][1];
int x = l[i];
++u, ++v;
edges[u].push_back({v, x});
edges[v].push_back({u, x});
}
decomp (1);
return (ans == 1e9 ? -1 : ans);
}
