#include "Aoi.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<endl
#define dout(a) cout<<a<<' '<<#a<<endl
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
using namespace std;
struct edge{
int to, w, dex;
};
namespace {
signed variable_example = 0;
signed function_example(signed a, signed b) { return a + b; }
const signed mxn = 10005;
vvi dist(mxn), from(mxn);
vb autism(mxn * 2);
vector<vector<edge>>adj(mxn);
const int lg = 9;
const int NL = 500;
string nl = "11";
void gen_dist(int v){
priority_queue<pair<int,int>>q;
dist[v].resize(mxn); from[v].resize(mxn);
f0r(i, mxn)dist[v][i] = 4e18;
q.push(mp(0,v)); dist[v][v]= 0; from[v][v] = -1;
while(!q.empty()){
int node = q.top().second; q.pop();
for(auto u : adj[node]){
int b = u.to; int w = u.w;
if(dist[v][b] > dist[v][node] + w){
from[v][b] = u.dex;
dist[v][b] = dist[v][node] + w;
q.push(mp(-dist[v][b], b));
}
}
}
}
string conv(int x){
// dout(x);
string ret = "";
for(int i = lg - 1; i >= 0; i--){
if((1<<i) & x)ret += '1';
else ret += '0';
}
return ret;
}
} // namespace
std::string aoi(signed N, signed M, signed Q, signed K, std::vector<signed> A,
std::vector<signed> B, std::vector<long long> C,
std::vector<signed> T, std::vector<signed> X) {
f0r(i, M){
adj[A[i]].pb({B[i], C[i], i});
adj[B[i]].pb({A[i], C[i], i});
}
sort(all(X));
// dout("SDFHSDF");
mii cmp; int cnt = 0;
for(auto u : X){
autism[u] = 1;
cmp[u] = cnt; cnt++;
}
gen_dist(0);
// f0r(i, N)cout<<dist[0][i]<<' '; cout<<'\n';
vb vau(M);
string ans = "";
for(auto x : T){
int cur = x;
vi au;
while(cur != 0){
int ed = from[0][cur];
if(A[ed] == cur){
cur = B[ed];
}
else cur = A[ed];
if(autism[ed]){
au.pb(cmp[ed]);
if(vau[ed])break;
vau[ed] = 1;
}
}
for(auto u : au){
ans += conv(u);
}
ans += nl;
}
// out(ans);
return ans;
}
#include "Bitaro.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<endl
#define dout(a) cout<<a<<' '<<#a<<endl
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
using namespace std;
struct edge{
int to, w, dex;
};
struct DSU{
int n; vi par, sz;
DSU(int x){
n=x; par.resize(n); sz.resize(n);
f0r(i,n)par[i] = i, sz[i] = 1;
}
int get(int x){
while(x != par[x])x = par[x];
return x;
}
void unite(int a, int b){
a = get(a); b = get(b);
if(a == b)return;
if(sz[a] < sz[b])swap(a,b); sz[a] += sz[b]; par[b] = a;
}
};
namespace {
const signed mxn = 10005;
vvi dist(mxn), from(mxn);
vb autism(mxn * 2);
vector<vector<edge>>adj(mxn);
vi par(mxn,-1);
const int lg = 9;
const int NL = 500;
void gen_dist(int v, int t1, int t2){
priority_queue<pair<int,int>>q;
dist[v].resize(mxn); from[v].resize(mxn);
f0r(i, mxn)dist[v][i] = 4e18, from[v][i] = -1;
q.push(mp(0,v)); dist[v][v]= 0; from[v][v] = -1;
while(!q.empty()){
int node = q.top().second; q.pop();
if(node == t1 || node == t2){
// dout(node);
return;
}
// dout2(node, dist[v][node]);
for(auto u : adj[node]){
int b = u.to; int w = u.w;
if(w >= 0 && dist[v][b] > dist[v][node] + w){
from[v][b] = u.dex;
dist[v][b] = dist[v][node] + w;
q.push(mp(-dist[v][b], b));
}
}
}
}
} // namespace
void bitaro(signed N, signed M, signed Q, signed K, std::vector<signed> A, std::vector<signed> B,
std::vector<long long> C, std::vector<signed> T, std::vector<signed> X,
std::string s) {
// DSU D = DSU(N);
f0r(i, M){
adj[A[i]].pb({B[i], C[i], i});
adj[B[i]].pb({A[i], C[i], i});
if(C[i] != -1){
// D.unite(A[i], B[i]);
}
}
sort(all(X));
mii cmp; int cnt = 0;
for(auto u : X){
autism[u] = 1;
cmp[u] = cnt; cnt++;
}
vvi tra(T.size());
int pt = 0;
int ii = 0;
// dout(s.size());
while(ii < s.size()){
// dout(i);
if(s[ii] == '1' && s[ii+1] == '1'){
pt++; ii+=2;
}
else{
int cur = 0;
for(int j = ii; j < ii + lg; j++){
cur += (1<<(lg - 1 - (j - ii))) * (s[j] - '0');
}
tra[pt].pb(cur);
ii += lg;
}
}
/*
for(int i = 0; i < s.size(); i += lg){
int cur = 0;
for(int j = i; j < i + lg; j++){
cur += (1<<(j - i)) * (s[j] - '0');
}
if(cur == NL)pt++;
else tra[pt].pb(cur);
}
*/
gen_dist(0, -1,-1);
f0r(i, N)par[i] = from[0][i];
int ptr = 0;
// f0r(i, N)cout<<from[0][i]<<' '; cout<<'\n';
for(auto vau : tra){
vector<signed>ans;
int cur = T[ptr];
// vout(vau);
for(auto ed : vau){
int save = cur;
ed = X[ed];
// if(dist[cur].size() == 0){
gen_dist(cur, A[ed], B[ed]);
// }
int a, b;
/*
if(D.get(cur) == D.get(A[ed])){
a = A[ed]; b = B[ed];
}
else b = A[ed]; a = B[ed];
*/
if(dist[cur][A[ed]] < dist[cur][B[ed]]){
a = A[ed]; b = B[ed];
}
else{
b = A[ed]; a = B[ed];
}
// dout2(a,b);
// if(dist[a].size() == 0){
gen_dist(a, cur, cur);
// }
while(cur != a){
ans.pb(from[a][cur]);
par[cur] = from[a][cur];
if(A[from[a][cur]] == cur){
cur = B[from[a][cur]];
}
else cur = A[from[a][cur]];
}
par[a] = ed;
ans.pb(ed);
cur = b;
}
int save = 0;
while(cur != 0){
ans.pb(par[cur]);
if(A[par[cur]] == cur){
cur = B[par[cur]];
}
else cur = A[par[cur]];
}
// vout(ans);
reverse(all(ans));
// vout(ans);
answer(ans);
ptr++;
}
// while(true){
//
// }
}
