#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define int long long
#define ld long double
#define pb push_back
#define rg ranges
#include "Aoi.h"
using namespace std;
namespace {
int n;
int m;
int q;
int k;
vector<vector<pair<int, int>>> g;
vector<int> t, x, dist;
void getDist() {
}
}
std::string aoi(int32_t N, int32_t M, int32_t Q, int32_t K, std::vector<int32_t> A,
std::vector<int32_t> B, std::vector<long long> C,
std::vector<int32_t> T, std::vector<int32_t> X) {
n = N, m = M, q = Q, k = K;
repIn(i, T) t.pb(i);
repIn(i, X) x.pb(i);
rep(i, 0, m) {
int a = A[i], b = B[i], c = C[i];
g[a].pb({b, c});
g[b].pb({a, c});
}
string ans;
repIn(i, t) {
string s;
int x = C[i];
rep(_, 0, 40) s += (char)(x % 2 + '0'), x /= 2;
rg::reverse(s);
ans += s;
}
return ans;
}
#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 1;
#include "Bitaro.h"
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define int long long
#define ld long double
#define pb push_back
#define rg ranges
using namespace std;
constexpr int inf = 1e18;
namespace {
int n;
int m;
int q;
int k;
vector<vector<pair<int, int>>> g;
vector<int> t, x;
vector<pair<int, int>> dist;
map<pair<int, int>, int> mp;
void getDist() {
dist.resize(n, {inf, -1});
dist[0] = {0, 0};
priority_queue<pair<int, int>> q;
q.push({0, 0});
while(q.size()) {
auto [d, v] = q.top();
q.pop();
d *= -1;
if(dist[v].first != d) continue;
repIn2(u, c, g[v]) if(dist[u].first > d + c) dist[u] = {d, v}, q.push({-(d + c), u});
}
}
}
void bitaro(int32_t N, int32_t M, int32_t Q, int32_t K, std::vector<int32_t> A,
std::vector<int32_t> B, std::vector<long long> C,
std::vector<int32_t> T, std::vector<int32_t> X, string s) {
n = N, m = M, q = Q, k = K;
repIn(i, T) t.pb(i);
repIn(i, X) x.pb(i);
auto it = s.begin();
repIn(i, t) {
int x = 0;
rep(_, 0, 40) x = x * 2 + (int)(*(it++) - '0');
C[i] = x;
}
rep(i, 0, m) {
int a = A[i], b = B[i], c = C[i];
g[a].pb({b, c});
g[b].pb({a, c});
mp[{a, b}] = i;
mp[{b, a}] = i;
}
getDist();
repIn(s, X) {
vector<int> ans;
ans.pb(s);
while(ans.back()) ans.pb(dist[ans.back()].second);
vector<int32_t> ans2;
rep(i, 1, ans.size()) {
auto v = ans[i], u = ans[i - 1];
ans2.pb(mp[{v, u}]);
}
rg::reverse(ans2);
answer(ans2);
}
}
