#include "Annalib.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef vector<vi> vvi;
const ll infinity = 4e18;
vi Dijkstra(int start, vector<vii> &graph) {
priority_queue<pii, vii, greater<pii>> pq;
pq.push({0, start});
int n = graph.size();
vi dist(n, infinity);
dist[start] = 0;
while (!pq.empty()) {
auto [d, node] = pq.top();
pq.pop();
if (d > dist[node]) continue;
for (auto [neighbor, w] : graph[node]) {
if (d + w < dist[neighbor]) {
pq.push({d + w, neighbor});
dist[neighbor] = d + w;
}
}
}
return dist;
}
void Send(int j, int len) {
while (len--) {
Tap(j & 1);
j >>= 1;
}
}
void Anna(int n, int m, int a[], int b[], ll c[], int q, int s[], int t[], int k, int u[]) {
vector<vii> graph(n), inv_graph(n);
vi ok(m, 1);
for (int i = 0; i < k; i++) ok[u[i]] = 0;
for (int i = 0; i < m; i++) {
if (ok[i]) {
graph[a[i]].push_back({b[i], c[i]});
inv_graph[b[i]].push_back({a[i], c[i]});
}
}
vvi vals(15, {infinity});
for (int i = 0; i < q; i++) {
vi d1 = Dijkstra(s[i], graph);
vi d2 = Dijkstra(t[i], inv_graph);
vi d(k + 1);
d[k] = d1[t[i]];
for (int j = 0; j < k; j++) d[j] = min(d1[a[u[j]]] + d2[b[u[j]]], infinity);
int ind = 0;
for (int j = 0; j < k; j++) {
for (int l = j + 1; l <= k; l++) {
vals[ind++].push_back(d[l] - d[j]);
}
}
}
vi real(15);
int ind = 0;
for (int j = 0; j < k; j++) {
for (int l = j + 1; l <= k; l++) {
real[ind++] = c[u[j]] - (l == k ? 0 : c[u[l]]);
}
}
for (int i = 0; i < (k + 1) * k / 2; i++) {
sort(all(vals[i]));
int j = lower_bound(all(vals[i]), real[i]) - vals[i].begin();
Send(j, 8);
}
}
#include "Brunolib.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef vector<vi> vvi;
const ll infinity2 = 4e18;
pair<vi, vii> Dijkstra(int start, vector<vector<tuple<int, ll, int>>> &graph) {
priority_queue<pii, vii, greater<pii>> pq;
pq.push({0, start});
int n = graph.size();
vi dist(n, infinity2);
vii prev(n, {-1, -1});
dist[start] = 0;
while (!pq.empty()) {
auto [d, node] = pq.top();
pq.pop();
if (d > dist[node]) continue;
for (auto [neighbor, w, ind] : graph[node]) {
if (d + w < dist[neighbor]) {
pq.push({d + w, neighbor});
dist[neighbor] = d + w;
prev[neighbor] = {node, ind};
}
}
}
return {dist, prev};
}
int Read(int l, int r, vi &x) {
int ans = 0;
for (int i = r - 1; i >= l; i--) {
ans = (ans << 1) + x[i];
}
return ans;
}
vi GetPath(int node, vii &prev) {
vi ans;
while (prev[node].first != -1) {
ans.push_back(prev[node].second);
node = prev[node].first;
}
reverse(all(ans));
return ans;
}
void Bruno(int n, int m, int a[], int b[], ll c[], int q, int s[], int t[], int k, int u[], int L, int X[]) {
vi x(L);
for (int i = 0; i < L; i++) x[i] = X[i];
vector<vector<tuple<int, ll, int>>> graph(n), inv_graph(n);
vi ok(m, 1);
for (int i = 0; i < k; i++) ok[u[i]] = 0;
for (int i = 0; i < m; i++) {
if (ok[i]) {
graph[a[i]].push_back({b[i], c[i], i});
inv_graph[b[i]].push_back({a[i], c[i], i});
}
}
vvi vals(15, {infinity2});
for (int i = 0; i < q; i++) {
auto [d1, p1] = Dijkstra(s[i], graph);
auto [d2, p2] = Dijkstra(t[i], inv_graph);
vi d(k + 1);
d[k] = d1[t[i]];
for (int j = 0; j < k; j++) d[j] = min(d1[a[u[j]]] + d2[b[u[j]]], infinity2);
int ind = 0;
for (int j = 0; j < k; j++) {
for (int l = j + 1; l <= k; l++) {
vals[ind++].push_back(d[l] - d[j]);
}
}
}
vi real(15);
for (int i = 0; i < (k + 1) * k / 2; i++) {
sort(all(vals[i]));
real[i] = vals[i][Read(8 * i, 8 * (i + 1), x)];
}
for (int i = 0; i < q; i++) {
auto [d1, p1] = Dijkstra(s[i], graph);
auto [d2, p2] = Dijkstra(t[i], inv_graph);
vi d(k + 1);
d[k] = d1[t[i]];
for (int j = 0; j < k; j++) d[j] = min(d1[a[u[j]]] + d2[b[u[j]]], infinity2);
int ind = 0;
vi bad(k + 1);
for (int j = 0; j < k; j++) {
for (int l = j + 1; l <= k; l++) {
if (real[ind++] <= d[l] - d[j]) bad[l] = 1;
else bad[j] = 1;
}
}
int j;
for (j = 0; bad[j]; j++);
vi path;
if (j < k) {
path = GetPath(a[u[j]], p1);
path.push_back(u[j]);
vi path2 = GetPath(b[u[j]], p2);
reverse(all(path2));
for (int y : path2) path.push_back(y);
} else {
path = GetPath(t[i], p1);
}
for (int y : path) Answer(y);
Answer(-1);
}
}
