#include "Aoi.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define fi first
#define se second
#define iii array<int,3>
#define pq_min(a) priority_queue<a,vector<a>,greater<a>>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
using namespace std;
const ll inf=1e18;
string aoi(int N, int M, int Q, int K, vector<int> A,
vector<int> B, vector<long long> C,
vector<int> T, vector<int> X) {
string s;
rep(i,0,K) repr(j,40,0) s+=(((C[i]>>j)&1)+'0');
return s;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define iii array<ll,3>
#define pq_min(a) priority_queue<a,vector<a>,greater<a>>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define ll long long int
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std;
const ll inf=1e18;
void bitaro(int N, int M, int Q, int K, vector<int> A, vector<int> B,
vector<long long> C, vector<int> T, vector<int> X,
string s) {
vector<iii> adj[N];
int ind=0;
rep(i,0,K){
repr(j,40,0){
C[i]+=(1<<j)*(s[ind]=='1');
ind++;
}
}
rep(i,0,M){
adj[A[i]].pb({B[i],C[i],i});
adj[B[i]].pb({A[i],C[i],i});
}
ll dis[N];
pii par[N];
rep(i,0,N) dis[i]=inf;
pq_min(pll) pq;
pq.push({0,0});
dis[0]=0;
par[0]={-1,-1};
while(pq.size()){
ll w=pq.top().fi, u=pq.top().se;
pq.pop();
if(dis[u]>w) continue;
repa(v,adj[u]){
if(dis[v[0]]>w+v[1]){
dis[v[0]]=v[1]+w;
par[v[0]]={u,v[2]};
pq.push({dis[v[0]],v[0]});
}
}
}
rep(i,0,Q){
vector<int> pth;
do{
pth.pb(par[T[i]].se);
T[i]=par[T[i]].fi;
}while(par[T[i]].fi!=-1);
reverse(all(pth));
answer(pth);
}
}
