#include "Annalib.h"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INFLL (3700000000000000099ll)
#define MAXN (305)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
static void write(int N) {
for(int i = 0; i < 7; i++) Tap((N & (1<<i)) ? 1 : 0);
}
static vector<int> VQ[6];
static ll rd[MAXN][MAXN];
static ll d[MAXN][MAXN];
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
for(int i = 0; i < N; i++) fill(d[i], d[i]+MAXN, INFLL);
for(int i = 0; i < M; i++) d[A[i]][B[i]] = C[i];
for(int i = 0; i < K; i++) d[A[U[i]]][B[U[i]]] = INFLL;
for(int i = 0; i < N; i++) d[i][i] = 0;
for(int k = 0; k < N; k++) for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) upmin(d[i][j], d[i][k]+d[k][j]);
for(int i = 0; i < N; i++) fill(rd[i], rd[i]+MAXN, INFLL);
for(int i = 0; i < M; i++) rd[A[i]][B[i]] = C[i];
for(int i = 0; i < N; i++) d[i][i] = 0;
for(int k = 0; k < N; k++) for(int i = 0; i < N; i++) for(int j = 0; j < N; j++)
upmin(rd[i][j], rd[i][k] + rd[k][j]);
for(int i = 0; i < Q; i++) {
bool flag = false;
for(int j = 0; j < K; j++)
if(rd[S[i]][T[i]] == d[S[i]][A[U[j]]] + C[U[j]] + d[B[U[j]]][T[i]]) {
flag = true; VQ[j].pb(i);
}
if(!flag) VQ[5].pb(i);
}
for(int i = 0; i <= 5; i++) write(sz(VQ[i]));
}
#include "Brunolib.h"
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INFLL (3700000000000000099ll)
#define MAXN (305)
#define MAXQ (65)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef __int128_t lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
const lll INFLLL = (lll)INFLL * MAXN * MAXN;
static unordered_map<int, int> HASH[61][61][61]; static int HASHn = 0;
static int HA[537824+5], HB[537824+5], HC[537824+5], HD[537824+5], HE[537824+5];
static lll dp[62][537824+5];
static int rdp[62][537824+5];
static bool chk[62][537824+5];
static ll d[MAXN][MAXN];
static ll rawd[MAXN][MAXN];
static int rawidx[MAXN][MAXN];
static ll Y[MAXQ][5];
static int X[1005], Xn = 0, L;
static int AnsQ[MAXQ];
static int Qsz[6];
static int readBit() { return X[Xn++]; }
static int readNum() {
int ret = 0; for(int i = 0; i < 7; i++) ret += readBit() ? (1<<i) : 0;
return ret;
}
static void f(vector<int>& V, const int N, int S, int E) {
if(S == E) return;
if(d[S][E] == rawd[S][E] && -1 != rawidx[S][E]) { V.pb(rawidx[S][E]); return; }
for(int i = 0; i < N; i++) {
if(i == S || i == E) continue;
if(d[S][E] == d[S][i] + d[i][E]) {
f(V, N, S, i); f(V, N, i, E);
return;
}
}
}
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[]) {
for(int i = 0; i < N; i++) fill(d[i], d[i]+MAXN, INFLL);
for(int i = 0; i < M; i++) if(-1 != C[i]) d[A[i]][B[i]] = C[i];
for(int i = 0; i < N; i++) d[i][i] = 0;
for(int k = 0; k < N; k++) for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) upmin(d[i][j], d[i][k]+d[k][j]);
for(int i = 0; i < N; i++) fill(rawd[i], rawd[i]+MAXN, -1);
for(int i = 0; i < M; i++) rawd[A[i]][B[i]] = C[i];
for(int i = 0; i < N; i++) fill(rawidx[i], rawidx[i]+MAXN, -1);
for(int i = 0; i < M; i++) rawidx[A[i]][B[i]] = i;
L = _L; for(int i = 0; i < L; i++) X[i] = _X[i];
for(int i = 0; i <= 5; i++) Qsz[i] = readNum();
for(int i = 0; i < Q; i++) for(int j = 0; j < 5; j++)
Y[i][j] = d[S[i]][T[i]] - (d[S[i]][A[U[j]]] + d[B[U[j]]][T[i]]);
for(int a = 0; a <= Qsz[0]; a++) for(int b = 0; b <= Qsz[1]; b++) for(int c = 0; c <= Qsz[2]; c++)
for(int d = 0; d <= Qsz[3]; d++) for(int e = 0; e <= Qsz[4]; e++) {
HA[HASHn] = a; HB[HASHn] = b; HC[HASHn] = c; HD[HASHn] = d; HE[HASHn] = e;
HASH[a][b][c][61*d+e] = HASHn++;
}
for(int i = 0; i <= Q; i++) fill(dp[i], dp[i]+537824+5, -INFLLL);
for(int i = 0; i <= Q; i++) fill(rdp[i], rdp[i]+537824+5, -1);
chk[0][0] = true; dp[0][0] = 0;
for(int i = 0; i < Q; i++) {
lll bt;
for(int j = 0; j < HASHn; j++) {
if(!chk[i][j]) continue;
int a = HA[j], b = HB[j], c = HC[j], d = HD[j], e = HE[j], idx;
if(a+1 <= Qsz[0]) {
idx = HASH[a+1][b][c][61*d+e];
chk[i+1][idx] = true;
bt = dp[i][j] + Y[i][0];
if(dp[i+1][idx] < bt) {
dp[i+1][idx] = bt; rdp[i+1][idx] = 0;
}
}
if(b+1 <= Qsz[1]) {
idx = HASH[a][b+1][c][61*d+e];
chk[i+1][idx] = true;
bt = dp[i][j] + Y[i][1];
if(dp[i+1][idx] < bt) {
dp[i+1][idx] = bt; rdp[i+1][idx] = 1;
}
}
if(c+1 <= Qsz[2]) {
idx = HASH[a][b][c+1][61*d+e];
chk[i+1][idx] = true;
bt = dp[i][j] + Y[i][2];
if(dp[i+1][idx] < bt) {
dp[i+1][idx] = bt; rdp[i+1][idx] = 2;
}
}
if(d+1 <= Qsz[3]) {
idx = HASH[a][b][c][61*(d+1)+e];
chk[i+1][idx] = true;
bt = dp[i][j] + Y[i][3];
if(dp[i+1][idx] < bt) {
dp[i+1][idx] = bt; rdp[i+1][idx] = 3;
}
}
if(e+1 <= Qsz[4]) {
idx = HASH[a][b][c][61*d+e+1];
chk[i+1][idx] = true;
bt = dp[i][j] + Y[i][4];
if(dp[i+1][idx] < bt) {
dp[i+1][idx] = bt; rdp[i+1][idx] = 4;
}
}
chk[i+1][j] = true;
if(dp[i+1][j] < dp[i][j]) {
dp[i+1][j] = dp[i][j]; rdp[i+1][j] = 5;
}
}
}
for(int i = Q, a = Qsz[0], b = Qsz[1], c = Qsz[2], d = Qsz[3], e = Qsz[4]; i; i--) {
AnsQ[i-1] = rdp[i][HASH[a][b][c][d*61+e]];
if(0 == AnsQ[i-1]) a--;
else if(1 == AnsQ[i-1]) b--;
else if(2 == AnsQ[i-1]) c--;
else if(3 == AnsQ[i-1]) d--;
else if(4 == AnsQ[i-1]) e--;
}
for(int i = 0; i < Q; i++) {
vector<int> V;
if(5 == AnsQ[i]) {
f(V, N, S[i], T[i]);
} else {
f(V, N, S[i], A[U[AnsQ[i]]]);
V.pb(U[AnsQ[i]]);
f(V, N, B[U[AnsQ[i]]], T[i]);
}
for(int v : V) Answer(v);
Answer(-1);
}
}
