#include<bits/stdc++.h>
#define MAXN 20007
#include "Aoi.h"
using namespace std;
namespace alice{
const long long inf=1e17;
int n,m,k,q,num;
vector< pair<int,int> > v[MAXN],tree[MAXN];
int comp[MAXN];
string ans;
bool block[MAXN],vis[MAXN];
long long dist[MAXN],cost[MAXN];
int parent[MAXN],up[MAXN],where[MAXN],special[MAXN];
priority_queue< pair<long long,int> , vector< pair<long long,int> > , greater < pair<long long,int> > > pq;
void dijkstra(int x){
for(int i=0;i<n;i++)dist[i]=inf;
dist[x]=0;
pq.push({dist[x],x});
while(!pq.empty()){
int minv=pq.top().second;
pq.pop();
if(vis[minv])continue;
vis[minv]=true;
for(auto e:v[minv]){
if(vis[e.first] or dist[e.first]<=dist[minv]+cost[e.second])continue;
dist[e.first]=dist[minv]+cost[e.second];
parent[e.first]=minv; up[e.first]=e.second;
pq.push({dist[e.first],e.first});
}
}
}
int dfs(int x,int edge){
vector<int> children;
for(auto e:tree[x]){
int y=dfs(e.first,e.second);
if(y!=-1)children.push_back(y);
}
int ver=special[x];
if(!children.empty() and ver==-1){
ver=children.back();
children.pop_back();
}
int last=ver;
for(int i:children){
comp[last]=num;
comp[i]=num;
last=num; num++;
}
if(x!=0 and block[edge] and last!=-1){
where[edge]=last;
}
return last;
}
string tonum(int x,int bits){
string s;
for(int i=0;i<bits;i++){
s.push_back(x%2+'0');
x/=2;
}
reverse(s.begin(),s.end());
return s;
}
};
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){
using namespace alice;
n=N; m=M; q=Q; k=K;
num=q;
for(int i=0;i<m;i++){
v[A[i]].push_back({B[i],i});
v[B[i]].push_back({A[i],i});
cost[i]=C[i];
}
for(int i=0;i<n;i++)special[i]=-1;
for(int i=0;i<T.size();i++)special[T[i]]=i;
for(int i:X){
block[i]=true; where[i]=31;
}
dijkstra(0);
for(int i=1;i<n;i++){
tree[parent[i]].push_back({i,up[i]});
}
dfs(0,-1);
comp[num-1]=0;
for(int i=0;i<num;i++){
ans+=tonum(comp[i],5);
}
for(int i=0;i<k;i++){
ans+=tonum(where[X[i]],5);
}
return ans;
}
#include<bits/stdc++.h>
#define MAXN 20007
#include "Bitaro.h"
using namespace std;
namespace bob{
const long long inf=1e17;
int n,m,k,q,num;
vector< pair<int,int> > v[MAXN];
vector<int> comp[MAXN],used[MAXN];
string ans;
bool block[MAXN],vis[MAXN];
long long dist[MAXN],cost[MAXN];
int parent[MAXN],up[MAXN],where[MAXN],special[MAXN];
priority_queue< pair<long long,int> , vector< pair<long long,int> > , greater < pair<long long,int> > > pq;
void dijkstra(int x){
for(int i=0;i<n;i++){
dist[i]=inf; vis[i]=false;
}
dist[x]=0;
pq.push({dist[x],x});
while(!pq.empty()){
int minv=pq.top().second;
pq.pop();
if(vis[minv])continue;
vis[minv]=true;
for(auto e:v[minv]){
if(vis[e.first] or dist[e.first]<=dist[minv]+cost[e.second])continue;
dist[e.first]=dist[minv]+cost[e.second];
parent[e.first]=minv; up[e.first]=e.second;
pq.push({dist[e.first],e.first});
}
}
}
vector<int> path(int x){
vector<int> res;
while(x!=0){
res.push_back(up[x]);
x=parent[x];
}
reverse(res.begin(),res.end());
return res;
}
void dfs(int x,int id){
if(x<q)used[x].push_back(id);
for(int i:comp[x]){
dfs(i,id);
}
}
string tonum(int x,int bits){
string s;
for(int i=0;i<bits;i++){
s.push_back(x%2+'0');
x/=2;
}
reverse(s.begin(),s.end());
return s;
}
};
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){
using namespace bob;
n=N; m=M; q=Q; k=K;
for(int i:X)block[i]=true;
for(int i=0;i<n;i++)special[i]=-1;
for(int i=0;i<T.size();i++)special[T[i]]=i;
for(int i=0;i<m;i++){
v[A[i]].push_back({B[i],i});
v[B[i]].push_back({A[i],i});
cost[i]=C[i];
}
for(int i=0;i<2*q-1;i++){
int curr=0;
for(int f=5*i;f<5*i+5;f++){
curr*=2; curr+=s[f]-'0';
}
if(curr!=0 and curr!=31)comp[curr].push_back(i);
}
for(int i=0;i<k;i++){
int curr=0;
for(int f=5*(2*q-1)+5*i;f<5*(2*q-1)+5*i+5;f++){
curr*=2; curr+=s[f]-'0';
}
where[i]=curr;
}
for(int i=0;i<k;i++){
dfs(where[i],i);
}
for(int i=0;i<q;i++){
for(int f:X)cost[f]=inf;
for(int f:used[i])cost[X[f]]=0;
dijkstra(0);
answer(path(T[i]));
}
return;
}
