#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
#define PB push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
namespace {
vector<pii> edges[2002];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int dist[1000002], odw[1000002];
int lastdist, mydist, myindx;
bool indx;
int poz, pot, val, gl_N;
void encode(int x, int format) {
for (int i = 0; i < format; i++) {
SendA(x%2);
x /= 2;
}
}
void run() {
pii para;
while (true) {
if (pq.empty())
return;
para = pq.top();
if (!odw[para.second])
break;
pq.pop();
}
int dis = para.first, v = para.second;
mydist = dis;
myindx = v;
encode(dis, 9);
indx = false; poz = 9, pot = 0, val = 0;
}
void updateEdges(int v) {
odw[v] = 1;
for (auto [u, d] : edges[v]) {
if (dist[u] > dist[v] + d) {
dist[u] = dist[v] + d;
pq.push({dist[u], u});
}
}
}
}
void ReceiveA(bool bit) {
val += (1<<pot) * bit;
pot++;
poz--;
if (!poz) {
if (indx) {
cerr << "Azer received index " << val << "\n";
dist[val] = lastdist;
updateEdges(val);
run();
} else {
cerr << "Azer received distance " << val << "\n";
lastdist = val;
if (mydist <= lastdist) {
cerr << "Time to act! (A)\n";
updateEdges(myindx);
encode(myindx, 11);
run();
} else {
cerr << "Not my turn (A)\n";
indx = true; poz = 11, pot = 0, val = 0;
}
}
}
}
void InitA(int N, int A, std::vector<signed> U, std::vector<signed> V, std::vector<signed> C) {
gl_N = N;
for (int i = 0; i < N; i++) {
dist[i] = 1000000001;
pq.push({dist[i], i});
}
for (int i = 0; i < A; i++) {
edges[U[i]].PB({V[i], C[i]});
edges[V[i]].PB({U[i], C[i]});
}
dist[0] = 0;
pq.push({0, 0});
run();
}
vector<signed> Answer() {
vector<signed> ans;
for (int i = 0; i < gl_N; i++) {
ans.PB(dist[i]);
}
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
#define PB push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
namespace {
vector<pii> edges[2002];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int dist[1000002], odw[1000002];
int lastdist, mydist, myindx;
bool indx;
int poz, pot, val, gl_N;
void encode(int x, int format) {
for (int i = 0; i < format; i++) {
SendB(x%2);
x /= 2;
}
}
void run() {
pii para;
while (true) {
if (pq.empty())
return;
para = pq.top();
if (!odw[para.second])
break;
pq.pop();
}
int dis = para.first, v = para.second;
mydist = dis;
myindx = v;
encode(dis, 9);
indx = false; poz = 9, pot = 0, val = 0;
}
void updateEdges(int v) {
odw[v] = 1;
for (auto [u, d] : edges[v]) {
if (dist[u] > dist[v] + d) {
dist[u] = dist[v] + d;
pq.push({dist[u], u});
}
}
}
}
void ReceiveB(bool bit) {
val += (1<<pot) * bit;
pot++;
poz--;
if (!poz) {
if (indx) {
cerr << "Baihan received index " << val << "\n";
dist[val] = lastdist;
updateEdges(val);
run();
} else {
cerr << "Baihan received distance " << val << "\n";
lastdist = val;
if (mydist < lastdist) {
cerr << "Time to act! (B)\n";
updateEdges(myindx);
encode(myindx, 11);
run();
} else {
cerr << "Not my turn (B)\n";
indx = true; poz = 11, pot = 0, val = 0;
}
}
}
}
void InitB(int N, int B, std::vector<int> U, std::vector<int> V, std::vector<int> D) {
gl_N = N;
for (int i = 0; i < N; i++) {
dist[i] = 1000000001;
pq.push({dist[i], i});
}
for (int i = 0; i < B; i++) {
edges[U[i]].PB({V[i], D[i]});
edges[V[i]].PB({U[i], D[i]});
}
dist[0] = 0;
pq.push({0, 0});
run();
}
