#include <algorithm>
#include <iostream>
#include "Azer.h"
using namespace std;
namespace {
const int N = 2000;
const int INF = 0x3f3f3f3f;
int *ej[N], *ew[N], eo[N], n;
int dd[N], pq[N], iq[N + 1], pq_cnt;
int d_, stage, ib, eb;
int counter;
void append(int i, int j, int w) {
int o = eo[i]++;
if (!o) {
ej[i] = (int *) malloc(sizeof *ej[i]);
ew[i] = (int *) malloc(sizeof *ew[i]);
} else if (!(o & o - 1)) {
ej[i] = (int *) realloc(ej[i], (o << 1) * sizeof *ej[i]);
ew[i] = (int *) realloc(ew[i], (o << 1) * sizeof *ew[i]);
}
ej[i][o] = j;
ew[i][o] = w;
}
bool lt(int i, int j) {
return dd[i] < dd[j];
}
int p2(int p) {
return (p <<= 1) > pq_cnt ? 0 : p ^ (p < pq_cnt && lt(iq[p ^ 1], iq[p]));
}
void pq_up(int i) {
int j, p, q;
for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int j, p, q;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add_last(int i) {
iq[pq[i] = ++pq_cnt] = i;
}
void pq_remove(int i) {
int j = iq[pq_cnt--];
if (i != j)
pq[j] = pq[i], pq_up(j), pq_dn(j);
pq[i] = 0;
}
void dijkstra(int i) {
pq_remove(i);
for (int o = 0; o < eo[i]; o++) {
int j = ej[i][o], w = ew[i][o], d = dd[i] + w;
if (dd[j] > d)
dd[j] = d, pq_up(j);
}
}
void run() {
if (!pq_cnt)
return;
int ea = dd[iq[1]] != INF ? dd[iq[1]] - d_ : 511;
stage = 0;
for (int h = 8; h >= 0; h--)
SendA(ea >> h & 1);
}
void receive(bool x) {
if (stage == 0) {
stage++;
if (x) {
int ia = iq[1]; d_ = dd[ia];
dijkstra(ia);
for (int h = 10; h >= 0; h--)
SendA(ia >> h & 1);
run();
} else
ib = 0;
} else if (stage < 12) {
ib = ib << 1 ^ x, stage++;
if (stage == 12)
eb = 0;
} else {
eb = eb << 1 ^ x, stage++;
if (stage == 21) {
d_ += eb;
if (dd[ib] > d_)
dd[ib] = d_, pq_up(ib);
dijkstra(ib);
run();
}
}
}
void init(int m, vector<int> ii, vector<int> jj, vector<int> ww) {
for (int h = 0; h < m; h++) {
int i = ii[h], j = jj[h], w = ww[h];
append(i, j, w), append(j, i, w);
}
for (int i = 0; i < n; i++)
dd[i] = INF;
dd[0] = 0;
for (int i = 0; i < n; i++)
pq_add_last(i);
run();
}
}
void InitA(int n, int m, vector<int> ii, vector<int> jj, vector<int> ww) {
::n = n, init(m, ii, jj, ww);
}
void ReceiveA(bool x) {
receive(x);
}
vector<int> Answer() {
vector<int> ans(n);
for (int i = 0; i < n; i++)
ans[i] = dd[i];
return ans;
}
#include <algorithm>
#include <iostream>
#include "Baijan.h"
using namespace std;
namespace {
const int N = 2000;
const int INF = 0x3f3f3f3f;
int *ej[N], *ew[N], eo[N], n;
int dd[N], pq[N], iq[N + 1], pq_cnt;
int d_, stage, ia, ea;
void append(int i, int j, int w) {
int o = eo[i]++;
if (!o) {
ej[i] = (int *) malloc(sizeof *ej[i]);
ew[i] = (int *) malloc(sizeof *ew[i]);
} else if (!(o & o - 1)) {
ej[i] = (int *) realloc(ej[i], (o << 1) * sizeof *ej[i]);
ew[i] = (int *) realloc(ew[i], (o << 1) * sizeof *ew[i]);
}
ej[i][o] = j;
ew[i][o] = w;
}
bool lt(int i, int j) {
return dd[i] < dd[j];
}
int p2(int p) {
return (p <<= 1) > pq_cnt ? 0 : p ^ (p < pq_cnt && lt(iq[p ^ 1], iq[p]));
}
void pq_up(int i) {
int j, p, q;
for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int j, p, q;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add_last(int i) {
iq[pq[i] = ++pq_cnt] = i;
}
void pq_remove(int i) {
int j = iq[pq_cnt--];
if (i != j)
pq[j] = pq[i], pq_up(j), pq_dn(j);
pq[i] = 0;
}
void dijkstra(int i) {
pq_remove(i);
for (int o = 0; o < eo[i]; o++) {
int j = ej[i][o], w = ew[i][o], d = dd[i] + w;
if (dd[j] > d)
dd[j] = d, pq_up(j);
}
}
void receive(bool x) {
if (stage < 9) {
ea = ea << 1 ^ x, stage++;
if (stage == 9) {
int ib = iq[1], eb = dd[ib] - d_;
if (ea < eb)
ia = 0, SendB(1);
else {
d_ = dd[ib];
dijkstra(ib);
stage = ea = 0;
SendB(0);
for (int h = 10; h >= 0; h--)
SendB(ib >> h & 1);
for (int h = 8; h >= 0; h--)
SendB(eb >> h & 1);
}
}
} else {
ia = ia << 1 ^ x, stage++;
if (stage == 20) {
d_ += ea;
if (dd[ia] > d_)
dd[ia] = d_, pq_up(ia);
dijkstra(ia);
stage = ea = 0;
}
}
}
void init(int m, vector<int> ii, vector<int> jj, vector<int> ww) {
for (int h = 0; h < m; h++) {
int i = ii[h], j = jj[h], w = ww[h];
append(i, j, w), append(j, i, w);
}
for (int i = 0; i < n; i++)
dd[i] = INF;
dd[0] = 0;
for (int i = 0; i < n; i++)
pq_add_last(i);
}
}
void InitB(int n, int m, vector<int> ii, vector<int> jj, vector<int> ww) {
::n = n, init(m, ii, jj, ww);
}
void ReceiveB(bool x) {
receive(x);
}
