#include "Annalib.h"
#define ull unsigned long long
#define INF 4000000000000000000LL
#include<stdio.h>
static ull w[301][301];
static bool v[90010];
static int R[61], cnt[5];
static int hc[62][6];
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
int i, j, k, x, y, xx, yy;
ull g;
for (i = 0; i < K; i++){
v[U[i]] = true;
}
for (i = 0; i < Q; i++)R[i] = -1;
for (i = 0; i < N; i++){
for (j = 0; j < N; j++){
if (i != j)w[i][j] = INF;
else w[i][j] = 0;
}
}
for (i = 0; i < M; i++){
if (!v[i])w[A[i]][B[i]] = C[i];
}
for (k = 0; k < N; k++){
for (i = 0; i < N; i++){
for (j = 0; j < N; j++){
if (w[i][j]>w[i][k] + w[k][j])w[i][j] = w[i][k] + w[k][j];
}
}
}
for (i = 0; i < K; i++){
x = A[U[i]], y = B[U[i]];
for (j = 0; j < Q; j++){
xx = S[j], yy = T[j];
g = w[xx][x] + w[y][yy] + C[U[i]];
if (w[xx][yy]>g){
w[xx][yy] = g;
R[j] = i;
}
}
}
for (i = 0; i < Q; i++){
if (R[i] != -1)cnt[R[i]]++;
}
hc[1][0]=1;
for(i=0;i<=Q+1;i++){
for(j=0;j<=K;j++){
if(i!=0){
hc[i][j]+=hc[i-1][j];
}
if(j!=0){
hc[i][j]+=hc[i][j-1];
}
}
}
j=0;
k=Q;
for (i = 0; i < K; i++){
k-=cnt[i];
j+=hc[k][K-i];
}
j=hc[Q+1][K]-j;
for(i=0;j;i++){
if(j>1){
Tap(j%2);
}
j/=2;
}
}
#include "Brunolib.h"
#define ull unsigned long long
#define INF 4000000000000000000LL
#include<stdio.h>
static ull w[310][310], w3[310][310];
static int w2[310][310];
static ull P[5][60];
static ull D[321293][2], G[6], cnt[6];
static int par[60][321293], Res[60];
static int n;
static int hc[62][6];
void Do(int a, int b)
{
int i;
ull gap = w[a][b];
while (1){
if (a == b)break;
for (i = 0; i < n; i++){
if (a != i && w2[a][i]&& w3[a][i] + w[i][b] == gap)break;
}
gap -= w3[a][i];
Answer(w2[a][i] - 1);
a = i;
}
}
void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
n = N;
int i, j, k, x, y;
ull t1, t2, t3;
for (i = 0; i < N; i++){
for (j = 0; j < N; j++){
if (i != j)w[i][j] = INF;
else w[i][j] = 0;
}
}
for (i = 0; i < M; i++){
if (C[i] != -1){
w[A[i]][B[i]] = C[i];
}
w2[A[i]][B[i]] = i + 1;
w3[A[i]][B[i]] = C[i];
}
for (k = 0; k < N; k++){
for (i = 0; i < N; i++){
for (j = 0; j < N; j++){
if (w[i][j]>w[i][k] + w[k][j])w[i][j] = w[i][k] + w[k][j];
}
}
}
for (i = 0; i < K; i++){
for (j = 0; j < Q; j++){
t1 = w[S[j]][T[j]];
t2 = w[S[j]][A[U[i]]];
t3 = w[B[U[i]]][T[j]];
if (t2 == INF || t3 == INF)continue;
if (t2 + t3 >= t1)continue;
P[i][j] = t1 - t2 - t3;
}
}
hc[1][0]=1;
for(i=0;i<=Q+1;i++){
for(j=0;j<=K;j++){
if(i!=0){
hc[i][j]+=hc[i-1][j];
}
if(j!=0){
hc[i][j]+=hc[i][j-1];
}
}
}
j=1;
for(i=0;i<L;i++){
j*=2;
j+=X[L-1-i];
}
j=hc[Q+1][K]-j+1;
G[0] = 1;
int l=Q;
for (i = 0; i < K; i++){
for(k=0;k<=Q;k++){
if(hc[k+1][K-i]>=j)break;
}
j-=hc[k][K-i];
cnt[i]=l-k;
l=k;
G[i + 1] = G[i] * (cnt[i] + 1);
}
for (i = 0; i < Q; i++){
for (j = 0; j < G[K]; j++)par[i][j] = -1;
for (j = G[K] - 1; j >= 0; j--){
if (j && (!D[j][0] && !D[j][1]))continue;
for (k = 0; k < K; k++){
if (!P[k][i])continue;
if ((j % G[k + 1]) / G[k] == cnt[k])continue;
t1 = D[j][0];
t2 = P[k][i] + D[j][1];
t1 += t2 >> 40, t2 &= ((1ll << 40) - 1);
if (D[j + G[k]][0] < t1 || (D[j + G[k]][0] == t1&&D[j + G[k]][1] < t2)){
D[j + G[k]][0] = t1;
D[j + G[k]][1] = t2;
par[i][j + G[k]] = k;
}
}
}
}
x = G[K] - 1, y = Q - 1;
for (i = 0; i < Q; i++)Res[i] = -1;
while (x){
if (par[y][x] == -1){
y--;
continue;
}
Res[y] = par[y][x];
x -= G[par[y][x]];
y--;
}
for (i = 0; i < Q; i++){
if (Res[i] == -1){
Do(S[i], T[i]);
}
else{
Do(S[i], A[U[Res[i]]]);
Answer(U[Res[i]]);
Do(B[U[Res[i]]], T[i]);
}
Answer(-1);
}
}
