#include "Annalib.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
static const int N=310;
static int f1[N][N], f2[N][N];
static const int inf=0x3f3f3f3f3f3f3f3f;
static int mask[60];
static mt19937 rng(69420);
void Anna(int32_t n, int32_t m, int32_t a[], int32_t b[], int c[], int32_t q, int32_t s[], int32_t t[], int32_t _k, int32_t u[]) {
memset(f1, 0x3f, sizeof f1);
memset(f2, 0x3f, sizeof f2);
for (int i=0; i<m; ++i){
f1[a[i]][b[i]]=c[i];
f2[a[i]][b[i]]=c[i];
}
for (int i=0; i<_k; ++i){
f2[a[u[i]]][b[u[i]]]=inf;
}
for (int i=0; i<n; ++i) f2[i][i]=0;
for (int k=0; k<n; ++k){
for (int i=0; i<n; ++i){
for (int j=0; j<n; ++j){
f1[i][j]=min(f1[i][j], f1[i][k]+f1[k][j]);
f2[i][j]=min(f2[i][j], f2[i][k]+f2[k][j]);
}
}
}
auto get_dist=[&](int id, int x, int y) -> int {
if (!id) return f2[x][y];
return min(inf, f2[x][a[u[id-1]]]+f2[b[u[id-1]]][y]);
};
for (int i=0; i<q; ++i){
for (int j=0; j<=_k; ++j) if (get_dist(j, s[i], t[i])<inf) mask[i]|=1<<j;
}
vector<pair<int, int>> order;
for (int i=0; i<=_k; ++i){
for (int j=i+1; j<=_k; ++j){
order.emplace_back(i, j);
}
}
shuffle(order.begin(), order.end(), rng);
if (_k==5){
order={
{0, 1},
{2, 3},
{4, 5},
{0, 2},
{0, 3},
{0, 4},
{0, 5},
{1, 2},
{1, 3},
{1, 4},
{1, 5},
{2, 4},
{2, 5},
{3, 4},
{3, 5},
};
}
for (auto &tmp:order){
int i=tmp.first, j=tmp.second;
vector<pair<int, int>> v;
for (int k=0; k<q; ++k){
if ((mask[k]>>i&1) && (mask[k]>>j&1)){
v.emplace_back(get_dist(i, s[k], t[k])-get_dist(j, s[k], t[k]), k);
}
}
sort(v.begin(), v.end());
if (v.empty()) continue;
int id=0;
int diff=(c[u[j-1]])-(i?c[u[i-1]]:0);
while (id!=v.size() && v[id].first<=diff) ++id;
for (int t=0; t<id; ++t) mask[v[t].second]^=1<<j;
for (int t=id; t<(int)v.size(); ++t) mask[v[t].second]^=1<<i;
int lg=32-__builtin_clz(v.size());
for (int l=0; l<lg; ++l) Tap(id>>l&1);
}
}
#include "Brunolib.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
static const int N=310;
static const int inf=0x3f3f3f3f3f3f3f3f;
static int id[6][6];
static int f[N][N], tr[N][N];
static int mask[60];
static mt19937 rng(69420);
void Bruno(int32_t n, int32_t m, int32_t a[], int32_t b[], int c[], int32_t q, int32_t s[], int32_t t[], int32_t _k, int32_t u[], int32_t _l, int32_t x[]) {
int cur=0;
memset(f, 0x3f, sizeof f);
for (int i=0; i<m; ++i) if (c[i]!=-1){
f[a[i]][b[i]]=c[i];
tr[a[i]][b[i]]=i;
}
for (int i=0; i<n; ++i) f[i][i]=0;
for (int k=0; k<n; ++k){
for (int i=0; i<n; ++i){
for (int j=0; j<n; ++j){
if (f[i][j]>f[i][k]+f[k][j]){
f[i][j]=f[i][k]+f[k][j];
tr[i][j]=tr[i][k];
}
}
}
}
auto get_dist=[&](int id, int x, int y) -> int {
if (!id) return f[x][y];
return min(inf, f[x][a[u[id-1]]]+f[b[u[id-1]]][y]);
};
auto get_path=[&](int x, int y) -> vector<int> {
vector<int> ans;
while (x!=y){
ans.push_back(tr[x][y]);
x=b[tr[x][y]];
}
return ans;
};
for (int i=0; i<q; ++i){
for (int j=0; j<=_k; ++j) if (get_dist(j, s[i], t[i])<inf) mask[i]|=1<<j;
}
vector<pair<int, int>> order;
for (int i=0; i<=_k; ++i){
for (int j=i+1; j<=_k; ++j){
order.emplace_back(i, j);
}
}
shuffle(order.begin(), order.end(), rng);
if (_k==5){
order={
{0, 1},
{2, 3},
{4, 5},
{0, 2},
{0, 3},
{0, 4},
{0, 5},
{1, 2},
{1, 3},
{1, 4},
{1, 5},
{2, 4},
{2, 5},
{3, 4},
{3, 5},
};
}
for (auto &tmp:order){
int i=tmp.first, j=tmp.second;
vector<pair<int, int>> v;
for (int k=0; k<q; ++k){
if ((mask[k]>>i&1) && (mask[k]>>j&1)){
v.emplace_back(get_dist(i, s[k], t[k])-get_dist(j, s[k], t[k]), k);
}
}
sort(v.begin(), v.end());
if (v.empty()) continue;
int lg=32-__builtin_clz(v.size());
for (int l=0; l<lg; ++l) id[i][j]|=x[cur++]<<l;
for (int l=0; l<id[i][j]; ++l) mask[v[l].second]^=1<<j;
for (int l=id[i][j]; l<(int)v.size(); ++l) mask[v[l].second]^=1<<i;
}
for (int i=0; i<q; ++i){
vector<int> ans;
if (mask[i]&1){
ans=get_path(s[i], t[i]);
}else{
int best=__builtin_ctz(mask[i])-1;
ans=get_path(s[i], a[u[0]]);
auto tmp=get_path(b[u[best]], t[i]);
ans.push_back(u[best]);
ans.insert(ans.end(), tmp.begin(), tmp.end());
}
for (int j:ans) Answer(j);
Answer(-1);
}
}
