//#include "grader.cpp"
#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace {
int variable_example = 0;
int function_example(int a, int b) { return a + b; }
} // namespace
std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
std::vector<int> B, std::vector<long long> C,
std::vector<int> T, std::vector<int> X) {
string S;
for(int i=0;i<K;i++){
for(int j=0;j<40;j++){
if(C[X[i]]&(1ll<<j)) S+="1";
else S+="0";
}
}
//cout<<S<<'\n';
return S;
}
//#include "grader.cpp"
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace {
const ll inf=(ll)1e18;
} // namespace
void bitaro(int n, int m, int q, int K, std::vector<int> A, std::vector<int> B,
std::vector<long long> C, std::vector<int> T, std::vector<int> X,
std::string S) {
for(int i=0;i<K;i++){
C[X[i]]=0;
for(int j=0;j<40;j++){
if(S[j+i*40]=='1') C[X[i]]+=(1ll<<j);
}
}
vector<vector<pair<int,pair<int,ll>>>> adj(n);
for(int i=0;i<m;i++){
//cout<<A[i]<<' '<<B[i]<<' '<<C[i]<<'\n';
adj[A[i]].push_back({B[i],{i,C[i]}});
adj[B[i]].push_back({A[i],{i,C[i]}});
}
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
vector<ll> d(n,inf);
vector<pair<int,int>> prv(n,{-1,-1});
d[0]=0;
pq.push({0,0});
while(!pq.empty()){
auto v=pq.top();
pq.pop();
if(v.f!=d[v.s]) continue;
for(auto u:adj[v.s]){
if(d[v.s]+u.s.s<d[u.f]){
prv[u.f]={v.s,u.s.f};
d[u.f]=d[v.s]+u.s.s;
pq.push({d[u.f],u.f});
}
}
}
for(int i=0;i<q;i++){
vector<int> res;
int cur=T[i];
while(cur!=0){
//cout<<prv[cur].s<<'\n';
res.push_back(prv[cur].s);
cur=prv[cur].f;
}
reverse(all(res));
answer(res);
}
}
