#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
typedef array<int, 2> ar2;
typedef vector<int> vi;
namespace {
const int N = 2000, A = 500, INF = N*A;
mt19937 rng(19260817);
int n;
int d[N];
bool marked[N];
vector<ar2> adj[N];
vector<bool> bits;
int last_d, i;
int state;
// 0: sent distance, waiting for response
// 1: got 1, waiting for distance and index
// 2: waiting for distance
// 3: sent 0, waiting for index
void spread(int i) {
marked[i] = true;
for (auto [j, c] : adj[i])
d[j] = min(d[j], d[i]+c);
last_d = d[i];
}
void init() {
i = -1;
for (int j = 0; j < n; j++) if (!marked[j] && (i == -1 || d[j] < d[i]))
i = j;
if (i == -1) return;
if (rng()%2 == 0) {
int v = min(A+1, d[i]-last_d);
for (int j = 0; j < 8; j++) SendA(v>>j&1);
state = 0;
} else {
state = 2;
}
}
void process(bool b) {
bits.push_back(b);
if (state == 0) {
assert(sz(bits) == 1);
if (bits[0] == 1) {
bits.clear();
state = 1;
} else {
bits.clear();
for (int j = 0; j < 11; j++) SendA(i>>j&1);
spread(i);
init();
}
} else if (state == 1) {
if (sz(bits) == 8+11) {
int v = 0;
for (int j = 0; j < 8; j++) v += int(bits[j])<<j;
i = 0;
for (int j = 0; j < 11; j++) i += int(bits[8+j])<<j;
bits.clear();
d[i] = last_d+v;
init();
}
} else if (state == 2) {
if (sz(bits) == 8) {
int v = 0;
for (int j = 0; j < 8; j++) v += int(bits[j])<<j;
bits.clear();
if (d[i]-last_d < v) {
SendA(1);
v = d[i]-last_d;
for (int j = 0; j < 8; j++) SendA(v>>j&1);
for (int j = 0; j < 11; j++) SendA(i>>j&1);
spread(i);
init();
} else {
state = 3, last_d += v;
SendA(0);
}
}
} else if (state == 3) {
if (sz(bits) == 11) {
i = 0;
for (int j = 0; j < 11; j++) i += int(bits[j])<<j;
bits.clear();
d[i] = last_d;
spread(i);
init();
}
}
}
}
void InitA(int n, int a, vi u, vi v, vi c) {
::n = n;
for (int i = 0; i < a; i++) {
adj[u[i]].push_back({v[i], c[i]});
adj[v[i]].push_back({u[i], c[i]});
}
fill(marked, marked+n, false);
fill(d, d+n, INF);
d[0] = 0;
spread(0);
init();
}
void ReceiveA(bool x) {
process(x);
}
vi Answer() {
return vi(d, d+n);
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
typedef array<int, 2> ar2;
typedef vector<int> vi;
namespace {
const int N = 2000, A = 500, INF = N*A;
mt19937 rng(19260817);
int n;
int d[N];
bool marked[N];
vector<ar2> adj[N];
vector<bool> bits;
int last_d, i;
int state;
// 0: sent distance, waiting for response
// 1: got 1, waiting for distance and index
// 2: waiting for distance
// 3: sent 0, waiting for index
void spread(int i) {
marked[i] = true;
for (auto [j, c] : adj[i])
d[j] = min(d[j], d[i]+c);
last_d = d[i];
}
void init() {
i = -1;
for (int j = 0; j < n; j++) if (!marked[j] && (i == -1 || d[j] < d[i]))
i = j;
if (i == -1) return;
if (rng()%2 == 1) {
int v = min(A+1, d[i]-last_d);
for (int j = 0; j < 8; j++) SendB(v>>j&1);
state = 0;
} else {
state = 2;
}
}
void process(bool b) {
bits.push_back(b);
if (state == 0) {
assert(sz(bits) == 1);
if (bits[0] == 1) {
bits.clear();
state = 1;
} else {
bits.clear();
for (int j = 0; j < 11; j++) SendB(i>>j&1);
spread(i);
init();
}
} else if (state == 1) {
if (sz(bits) == 8+11) {
int v = 0;
for (int j = 0; j < 8; j++) v += int(bits[j])<<j;
i = 0;
for (int j = 0; j < 11; j++) i += int(bits[8+j])<<j;
bits.clear();
d[i] = last_d+v;
init();
}
} else if (state == 2) {
if (sz(bits) == 8) {
int v = 0;
for (int j = 0; j < 8; j++) v += int(bits[j])<<j;
bits.clear();
if (d[i]-last_d < v) {
SendB(1);
v = d[i]-last_d;
for (int j = 0; j < 8; j++) SendB(v>>j&1);
for (int j = 0; j < 11; j++) SendB(i>>j&1);
spread(i);
init();
} else {
state = 3, last_d += v;
SendB(0);
}
}
} else if (state == 3) {
if (sz(bits) == 11) {
i = 0;
for (int j = 0; j < 11; j++) i += int(bits[j])<<j;
bits.clear();
d[i] = last_d;
spread(i);
init();
}
}
}
}
void InitB(int n, int a, vi u, vi v, vi c) {
::n = n;
for (int i = 0; i < a; i++) {
adj[u[i]].push_back({v[i], c[i]});
adj[v[i]].push_back({u[i], c[i]});
}
fill(marked, marked+n, false);
fill(d, d+n, INF);
d[0] = 0;
spread(0);
init();
}
void ReceiveB(bool x) {
process(x);
}
