#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
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) {
vector<int> parent(N, -1);
vector<ll> eee(N);
vector<long long> dist(N, -1);
priority_queue<tuple<ll, ll, ll, ll>> q;
q.push(make_tuple(0, 0, -1, -1));
vector<vector<tuple<ll, ll, ll>>> edges(N);
for(int i = 0; i < M; i++) {
ll a = A[i];
ll b = B[i];
ll c = C[i];
edges[a].push_back(make_tuple(b, c, i));
edges[b].push_back(make_tuple(a, c, i));
}
while(!q.empty()) {
ll d, node, p, eg;
tie(d, node, p, eg) = q.top();
d *= -1;
q.pop();
if(dist[node] != -1) continue;
dist[node] = d;
parent[node] = p;
eee[node] = eg;
for(tuple<ll, ll, ll> e : edges[node]) {
q.push(make_tuple(-(d + get<1>(e)), get<0>(e), node, get<2>(e)));
}
}
map<int, int> mp;
for(int i = 0; i < K; i++) {
mp[X[i]] = i;
}
string s(9 * K + 9 * Q, '1');
for(int i = 0; i < N; i++) {
if(mp.find(eee[i]) == mp.end()) continue;
ll current = parent[i];
while(current != -1) {
if(mp.find(eee[current]) != mp.end()) {
for(int j = 0; j < 9; j++) {
int r = mp[eee[i]];
s[9 * r + j] = (char) ((eee[current] >> j) & 1) + 48;
}
break;
}
current = parent[current];
}
}
for(int i = 0; i < Q; i++) {
ll current = T[i];
while(current != -1) {
if(mp.find(eee[current]) != mp.end()) {
for(int j = 0; j < 9; j++) {
s[9 * K + 9 * i + j] = (char) ((eee[current] >> j) & 1) + 48;
}
break;
}
current = parent[current];
}
}
// cout << s << "\n";
return s;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
namespace {
int variable_example = 0;
int function_example(int a, int b) { return a + b; }
} // 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) {
vector<ll> tree_parent(K);
for(int i = 0; i < K; i++) {
int a = 0;
for(int j = 0; j < 9; j++) {
a += ((int) (s[9 * i + j] - 48)) << j;
}
if(a == 511) a = -1;
tree_parent[i] = a;
}
/*cout << "\n";
for(int a : tree_parent) cout << a << " ";
cout << " <-tree\n";*/
for (int i = 0; i < Q; i++) {
vector<ll> newC = C;
int a = 0;
for(int j = 0; j < 9; j++) {
a += ((int) s[9 * (i + K) + j] - 48) << j;
}
if(a == 511) a = -1;
//cout << "\n" << a << "\n";
for(int j = 0; j < K; j++) {
newC[X[j]] = 0x7fffffffffff;
}
while(a != -1) {
newC[X[a]] = 0;
a = tree_parent[a];
}
//for(ll a : newC) cout << a << " ";
//cout << "\n";
vector<int> parent(N, -1);
vector<ll> eee(N);
vector<long long> dist(N, -1);
priority_queue<tuple<ll, ll, ll, ll>> q;
q.push(make_tuple(0, 0, -1, -1));
vector<vector<tuple<ll, ll, ll>>> edges(N);
for(int i = 0; i < M; i++) {
ll a = A[i];
ll b = B[i];
ll c = newC[i];
edges[a].push_back(make_tuple(b, c, i));
edges[b].push_back(make_tuple(a, c, i));
}
while(!q.empty()) {
ll d, node, p, eg;
tie(d, node, p, eg) = q.top();
d *= -1;
q.pop();
if(dist[node] != -1) continue;
dist[node] = d;
parent[node] = p;
eee[node] = eg;
for(tuple<ll, ll, ll> e : edges[node]) {
q.push(make_tuple(-(d + get<1>(e)), get<0>(e), node, get<2>(e)));
}
}
vector<int> v;
int node = T[i];
while(node != -1) {
if(eee[node] != -1) v.push_back(eee[node]);
node = parent[node];
}
reverse(v.begin(), v.end());
answer(v);
}
}
