#include "Annalib.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf = 3e18+1;
const ll mod2 = 1e9+7;
//const ll base=67;
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q;
int kk;
int el = 19;
ll dp[500][500];
int c[10000];
int a[10000];
int b[10000];
int s[10000];
int t[10000];
int u[10000];
int trace[500][500];
bool choose[500];
vector<int> g[500];
vector<pair<int,int>>send;
void rebuild()
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
dp[i][j]=inf;
dp[i][i]=0;
}
for(int i=1; i<=m; i++)
if(!choose[i])
dp[a[i]][b[i]]=c[i];
for(int mid=0; mid<n; mid++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
dp[i][j]=min(dp[i][j],dp[i][mid]+dp[mid][j]);
if(dp[i][j]==dp[i][mid]+dp[mid][j])
trace[i][j]=mid;
}
}
int cost(int u,int y)
{
if(y==0)return dp[s[u]][t[u]];
return dp[s[u]][a[y]]+dp[b[y]][t[u]];
}
int f(int x,int y,int z)
{
return cost(x,y)-cost(x,z);
}
bool cmp(int x,int y)
{
return f(x,root,now)<f(y,root,now);
}
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[])
{
n=N;
m=M;
k=K;
q=Q;
for(int i=1; i<=k; i++)
u[i]=U[i-1]+1;
for(int i=1; i<=q; i++)
s[i]=S[i-1],t[i]=T[i-1];
for(int i=1; i<=m; i++)
a[i]=A[i-1],b[i]=B[i-1],c[i]=C[i-1];
for(int i=1; i<=k; i++)
choose[u[i]]=1;
rebuild();
for(int i=1; i<=q; i++)
g[0].pb(i);
for(int i=1; i<=k; i++)
for(int j=0; j<i; j++)
{
root=u[i];
now=u[j];
sort(g[j].begin(),g[j].end(),cmp);
int pos=0;
while(true)
{
if(pos==g[j].size())break;
if(cost(g[j][pos],root)+c[root]>=cost(g[j][pos],now)+c[now]) break;
g[i].pb(g[j][pos]);
pos++;
}
for(int ff=0; ff<pos; ff++)
g[i].pb(g[j][ff]);
send.pb({pos,g[j].size()+1});
reverse(g[j].begin(),g[j].end());
while(pos!=0)
{
g[j].pop_back();
pos--;
}
}
long long total=0;
reverse(send.begin(),send.end());
for(auto x:send)
total=total*x.second+x.first;
while(total!=0)Tap(total&1),total/=2;
}
#include "Brunolib.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf =3e18+1;
const ll mod2 = 1e9+7;
//const ll base=67;
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q;
int kk;
int el = 19;
long long dp[500][500];
int c[10000];
int a[10000];
int b[10000];
int s[10000];
int t[10000];
int u[10000];
int trace[500][500];
bool choose[10000];
int cc[500][500];
vector<int> g[500],v,result[500];
void rebuild()
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
dp[i][j]=inf;
dp[i][i]=0;
}
for(int i=1; i<=m; i++)
if(!choose[i])
dp[a[i]][b[i]]=c[i];
for(int mid=0; mid<n; mid++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
dp[i][j]=min(dp[i][j],dp[i][mid]+dp[mid][j]);
if(dp[i][j]==dp[i][mid]+dp[mid][j])
trace[i][j]=mid;
}
}
int cost(int u,int y)
{
if(y==0)return dp[s[u]][t[u]];
return dp[s[u]][a[y]]+dp[b[y]][t[u]];
}
int f(int x,int y,int z)
{
return cost(x,y)-cost(x,z);
}
bool cmp(int x,int y)
{
return f(x,root,now)<f(y,root,now);
}
void dnc(int x,int y)
{
if(x==y) return;
if(dp[x][y]==inf) assert(0);
if(trace[x][y]==x||trace[x][y]==y)
{
v.pb(cc[x][y]);
return;
}
dnc(x,trace[x][y]);
dnc(trace[x][y],y);
}
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[])
{
long long total=0;
n=N;
m=M;
k=K;
q=Q;
for(int i=0; i<L; i++)
total=total+mask(i)*X[i];
for(int i=1; i<=k; i++)
u[i]=U[i-1]+1;
for(int i=1; i<=q; i++)
s[i]=S[i-1],t[i]=T[i-1];
for(int i=1; i<=m; i++)
a[i]=A[i-1],b[i]=B[i-1],c[i]=C[i-1],cc[a[i]][b[i]]=i-1;
for(int i=1; i<=k; i++)
choose[u[i]]=1;
rebuild();
for(int i=1; i<=q; i++)
g[0].pb(i);
for(int i=1; i<=k; i++)
for(int j=0; j<i; j++)
{
root=u[i];
now=u[j];
sort(g[j].begin(),g[j].end(),cmp);
int pos=total%(g[j].size()+1);
total/=(g[j].size()+1);
for(int ff=0; ff<pos; ff++)
g[i].pb(g[j][ff]);
reverse(g[j].begin(),g[j].end());
while(pos!=0)
{
g[j].pop_back();
pos--;
}
}
for(int i=0; i<=k; i++)
{
for(auto x:g[i])
{
if(i==0)dnc(s[x],t[x]);
else dnc(s[x],a[u[i]]),v.pb(u[i]-1),dnc(b[u[i]],t[x]);
result[x]=v;
v.clear();
}
}
for(int i=1;i<=q;i++)
{
result[i].pb(-1);
for(auto x:result[i])
Answer(x);
}
}
