#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
#define SZ(X) (int)(X).size()
using namespace std;
using LL = long long;
const int INF = 1e9;
const int SIZE = 200'001;
vector<pair<int, int>> e[SIZE];
int parent[SIZE];
int ll[SIZE], rr[SIZE], node_id;
LL depth[SIZE];
int edge_num[SIZE];
void dfs(int x, int lt) {
ll[x] = node_id++;
int ma = 0, ma_id = -1;
for (auto &[y, v] : e[x]) {
if (y == lt) continue;
depth[node_id] = depth[ll[x]] + v;
edge_num[node_id] = edge_num[ll[x]] + 1;
dfs(y, x);
if (ma < rr[y] - ll[y]) {
ma = rr[y] - ll[y];
ma_id = y;
}
}
if (ma_id != -1) parent[ma_id] = x;
rr[x] = node_id;
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N - 1; i++) {
e[H[i][0]].push_back({H[i][1], L[i]});
e[H[i][1]].push_back({H[i][0], L[i]});
}
fill(parent, parent + N, -1);
dfs(0, 0);
int an = INF;
for (int i = 0; i < N; i++) {
if (ll[i] + 1 < rr[i]) continue;
int x = i;
unordered_map<LL, int> mi;
mi[depth[ll[x]]] = edge_num[ll[x]];
auto test = [&](int id, int lca_id) {
LL need = K + 2 * depth[lca_id] - depth[id];
if (mi.count(need)) {
an = min(an, edge_num[id] + mi[need] - 2 * edge_num[lca_id]);
}
};
auto add = [&](int id) {
LL h = depth[id];
if (!mi.count(h)) {
mi[h] = edge_num[id];
} else {
mi[h] = min(mi[h], edge_num[id]);
}
};
add(ll[x]);
cout << x;
while (parent[x] != -1) {
int p = parent[x];
cout << ' ' << p;
for (auto [y, _] : e[p]) {
if (depth[ll[y]] < depth[ll[p]] || y == x) continue;
for (int j = ll[y]; j < rr[y]; j++) test(j, ll[p]);
for (int j = ll[y]; j < rr[y]; j++) add(j);
}
test(ll[p], ll[p]);
add(ll[p]);
x = p;
}
cout << '\n';
}
if (an == INF) an = -1;
return an;
}
