#include "Azer.h"
#include <bits/stdc++.h>
namespace {
using namespace std;
template <typename T>
using min_heap = priority_queue<T, vector<T>, less<T>>;
#define bit(n, i) (((n) >> (i)) & 1)
mt19937 rng(42);
int n;
vector<vector<pair<int, int>>> g;
int last = 0;
vector<bool> b;
vector<int> dist;
set<pair<int, int>> pq;
int state, ptr, curr;
int delta, delta_v;
const int X = 0;
void recalc(int v) {
for (auto [u, w] : g[v]) {
if (dist[u] == -1 || dist[u] > dist[v] + w) {
auto it = pq.find({dist[u], u});
if (it != pq.end()) {
pq.erase(it);
}
dist[u] = dist[v] + w;
pq.insert({dist[u], u});
}
}
}
void process() {
int delta1 = 0;
if (pq.empty()) {
delta1 = 501;
}
else {
auto [dist_v, v] = *pq.begin();
delta1 = dist_v - last;
}
for (int i = 0; i < 9; i++) {
SendA(bit(delta1, i));
}
state = 1;
ptr = 0;
delta = 0;
delta_v = 0;
}
}
void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
n = N;
g.resize(n);
for (int i = 0; i < A; i++) {
g[U[i]].push_back({V[i], C[i]});
g[V[i]].push_back({U[i], C[i]});
}
dist.assign(n, -1);
dist[0] = 0;
b.resize(n);
for (int i = 0; i < n; i++) {
b[i] = rng() % 2;
}
recalc(0);
curr = 1;
if (b[curr] == X) {
process();
}
else {
state = 0;
delta = 0;
ptr = 0;
}
}
void ReceiveA(bool x) {
if (state == 0) {
if (x) {
delta += 1 << ptr;
}
ptr++;
if (ptr == 9) {
int delta1 = 0, v;
if (pq.empty()) {
delta1 = 501;
v = 0;
}
else {
auto [dist_v, v1] = *pq.begin();
delta1 = dist_v - last;
v = v1;
}
if (delta1 < delta) {
SendA(true);
for (int i = 0; i < 9; i++) {
SendA(bit(delta1, i));
}
for (int i = 0; i < 11; i++) {
SendA(bit(v, i));
}
recalc(v);
pq.erase({dist[v], v});
last = dist[v];
curr++;
if (curr == n) {
}
else if (b[curr] == X) {
process();
}
else {
state = 0;
delta = 0;
ptr = 0;
}
}
else {
SendA(false);
state = 2;
delta_v = 0;
ptr = 0;
}
}
}
else if (state == 1) {
if (ptr == 0) {
if (x == 0) {
auto [dist_v, v] = *pq.begin();
recalc(v);
pq.erase(pq.begin());
for (int i = 0; i < 11; i++) {
SendA(bit(v, i));
}
last = dist[v];
curr++;
if (curr == n) {
}
else if (b[curr] == X) {
process();
}
else {
state = 0;
delta = 0;
ptr = 0;
}
}
else {
ptr++;
}
}
else if (ptr <= 9) {
if (x == 1) {
delta += 1 << (ptr - 1);
}
ptr++;
}
else if (ptr <= 20) {
if (x == 1) {
delta_v += 1 << (ptr - 10);
}
ptr++;
if (ptr == 21) {
int v = delta_v;
auto it = pq.find({dist[v], v});
if (it != pq.end()) {
pq.erase(it);
}
dist[v] = last + delta;
recalc(v);
last = dist[v];
curr++;
if (curr == n) {
}
else if (b[curr] == X) {
process();
}
else {
state = 0;
delta = 0;
ptr = 0;
}
}
}
}
else {
if (x) {
delta_v += 1 << ptr;
}
ptr++;
if (ptr == 11) {
int v = delta_v;
auto it = pq.find({dist[v], v});
if (it != pq.end()) {
pq.erase(it);
}
dist[v] = last + delta;
recalc(v);
last = dist[v];
curr++;
if (curr == n) {
}
else if (b[curr] == X) {
process();
}
else {
state = 0;
delta = 0;
ptr = 0;
}
}
}
}
vector<int> Answer() {
return dist;
}
#include "Baijan.h"
#include <bits/stdc++.h>
namespace {
using namespace std;
template <typename T>
using min_heap = priority_queue<T, vector<T>, less<T>>;
#define bit(n, i) (((n) >> (i)) & 1)
mt19937 rng(42);
int n;
vector<vector<pair<int, int>>> g;
int last = 0;
vector<bool> b;
vector<int> dist;
set<pair<int, int>> pq;
int state, ptr, curr;
int delta, delta_v;
const int X = 1;
void recalc(int v) {
for (auto [u, w] : g[v]) {
if (dist[u] == -1 || dist[u] > dist[v] + w) {
auto it = pq.find({dist[u], u});
if (it != pq.end()) {
pq.erase(it);
}
dist[u] = dist[v] + w;
pq.insert({dist[u], u});
}
}
}
void process() {
int delta1 = 0;
if (pq.empty()) {
delta1 = 501;
}
else {
auto [dist_v, v] = *pq.begin();
delta1 = dist_v - last;
}
for (int i = 0; i < 9; i++) {
SendB(bit(delta1, i));
}
state = 1;
ptr = 0;
delta = 0;
delta_v = 0;
}
}
void InitB(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
n = N;
g.resize(n);
for (int i = 0; i < A; i++) {
g[U[i]].push_back({V[i], C[i]});
g[V[i]].push_back({U[i], C[i]});
}
dist.assign(n, -1);
dist[0] = 0;
b.resize(n);
for (int i = 0; i < n; i++) {
b[i] = rng() % 2;
}
recalc(0);
curr = 1;
if (b[curr] == X) {
process();
}
else {
state = 0;
delta = 0;
ptr = 0;
}
}
void ReceiveB(bool x) {
if (state == 0) {
if (x) {
delta += 1 << ptr;
}
ptr++;
if (ptr == 9) {
int delta1 = 0, v;
if (pq.empty()) {
delta1 = 501;
v = 0;
}
else {
auto [dist_v, v1] = *pq.begin();
delta1 = dist_v - last;
v = v1;
}
if (delta1 < delta) {
SendB(true);
for (int i = 0; i < 9; i++) {
SendB(bit(delta1, i));
}
for (int i = 0; i < 11; i++) {
SendB(bit(v, i));
}
recalc(v);
pq.erase({dist[v], v});
last = dist[v];
curr++;
if (curr == n) {
}
else if (b[curr] == X) {
process();
}
else {
state = 0;
delta = 0;
ptr = 0;
}
}
else {
SendB(false);
state = 2;
delta_v = 0;
ptr = 0;
}
}
}
else if (state == 1) {
if (ptr == 0) {
if (x == 0) {
auto [dist_v, v] = *pq.begin();
recalc(v);
pq.erase(pq.begin());
for (int i = 0; i < 11; i++) {
SendB(bit(v, i));
}
last = dist[v];
curr++;
if (curr == n) {
}
else if (b[curr] == X) {
process();
}
else {
state = 0;
delta = 0;
ptr = 0;
}
}
else {
ptr++;
}
}
else if (ptr <= 9) {
if (x == 1) {
delta += 1 << (ptr - 1);
}
ptr++;
}
else if (ptr <= 20) {
if (x == 1) {
delta_v += 1 << (ptr - 10);
}
ptr++;
if (ptr == 21) {
int v = delta_v;
auto it = pq.find({dist[v], v});
if (it != pq.end()) {
pq.erase(it);
}
dist[v] = last + delta;
recalc(v);
last = dist[v];
curr++;
if (curr == n) {
}
else if (b[curr] == X) {
process();
}
else {
state = 0;
delta = 0;
ptr = 0;
}
}
}
}
else {
if (x) {
delta_v += 1 << ptr;
}
ptr++;
if (ptr == 11) {
int v = delta_v;
auto it = pq.find({dist[v], v});
if (it != pq.end()) {
pq.erase(it);
}
dist[v] = last + delta;
recalc(v);
last = dist[v];
curr++;
if (curr == n) {
}
else if (b[curr] == X) {
process();
}
else {
state = 0;
delta = 0;
ptr = 0;
}
}
}
}
