#include "Azer.h"
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
namespace {
using i64 = long long;
template <class T>
using vec = vector<T>;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;
int N, X, ff, cnt, lst, vis_cnt;
vec<int> dis;
priority_queue<pair<int, int>> pq;
vec<vec<pair<int, int>>> g;
void send_number(int x, int b) {
for (int i = b - 1; i >= 0; i--) {
SendA((x >> i) & 1);
}
}
void fix_pq_empty() {
if (vis_cnt == N) {
return;
}
if (empty(pq)) {
pq.emplace(-(lst + (1 << 9) - 1), N);
}
}
}
void InitA(int N, int A, vec<int> U, vec<int> V, vec<int> C) {
::N = N;
g.resize(N + 2);
dis.resize(N + 2, infty<int>);
for (int i = 0; i < A; i++) {
g[U[i]].emplace_back(V[i], C[i]);
g[V[i]].emplace_back(U[i], C[i]);
}
dis[0] = 0;
vis_cnt = 1;
for (auto [to, w] : g[0]) {
dis[to] = w;
pq.emplace(-(dis[to]), to);
}
fix_pq_empty();
SendA((-pq.top().first) >> 8 & 1);
}
void ReceiveA(bool x) {
if (ff == 0) {
if (cnt++ < 9) {
X = X * 2 + x;
if (cnt != 9) {
SendA((-pq.top().first - lst) >> (9 - cnt - 1) & 1);
}
else {
auto [d, i] = pq.top();
d = -d;
//cerr << "A " << d - lst << ' ' << X << '\n';
if (d - lst <= X) {
pq.pop();
vis_cnt += 1;
lst = d;
for (auto [to, w] : g[i]) {
if (dis[to] > dis[i] + w) {
pq.emplace(-(dis[to] = dis[i] + w), to);
}
}
send_number(i, 11);
while (!empty(pq) && -pq.top().first != dis[pq.top().second]) {
pq.pop();
}
fix_pq_empty();
if (!empty(pq)) {
SendA((-pq.top().first - lst) >> 8 & 1);
}
}
else {
ff = 1;
lst += X;
}
X = 0;
cnt = 0;
}
}
}
else {
if (cnt++ < 11) {
X = X * 2 + x;
if (cnt == 11) {
dis[X] = lst;
vis_cnt += 1;
for (auto [to, w] : g[X]) {
if (dis[to] > dis[X] + w) {
pq.emplace(-(dis[to] = dis[X] + w), to);
}
}
while (!empty(pq) && -pq.top().first != dis[pq.top().second]) {
pq.pop();
}
fix_pq_empty();
if (!empty(pq)) {
SendA((-pq.top().first - lst) >> 8 & 1);
}
cnt = 0;
ff = 0;
X = 0;
}
}
}
}
std::vector<int> Answer() {
return {begin(dis), begin(dis) + N};
}
#include "Baijan.h"
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
namespace {
using i64 = long long;
template <class T>
using vec = vector<T>;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;
int N, X, ff, cnt, lst, vis_cnt;
vec<int> dis;
priority_queue<pair<int, int>> pq;
vec<vec<pair<int, int>>> g;
void send_number(int x, int b) {
for (int i = b - 1; i >= 0; i--) {
SendB((x >> i) & 1);
}
}
void fix_pq_empty() {
if (vis_cnt == N) {
return;
}
if (empty(pq)) {
pq.emplace(-(lst + (1 << 9) - 1), N);
}
}
}
void InitB(int N, int A, vec<int> U, vec<int> V, vec<int> C) {
::N = N;
g.resize(N + 2);
dis.resize(N + 2, infty<int>);
for (int i = 0; i < A; i++) {
g[U[i]].emplace_back(V[i], C[i]);
g[V[i]].emplace_back(U[i], C[i]);
}
dis[0] = 0;
vis_cnt = 1;
for (auto [to, w] : g[0]) {
dis[to] = w;
pq.emplace(-(dis[to]), to);
}
fix_pq_empty();
}
void ReceiveB(bool x) {
if (ff == 0) {
if (cnt++ < 9) {
X = X * 2 + x;
SendB((-pq.top().first - lst) >> (9 - cnt) & 1);
if (cnt == 9) {
auto [d, i] = pq.top();
d = -d;
//cerr << "B " << d - lst << ' ' << X << '\n';
if (d - lst < X) {
pq.pop();
vis_cnt += 1;
lst = d;
for (auto [to, w] : g[i]) {
if (dis[to] > dis[i] + w) {
pq.emplace(-(dis[to] = dis[i] + w), to);
}
}
send_number(i, 11);
while (!empty(pq) && -pq.top().first != dis[pq.top().second]) {
pq.pop();
}
fix_pq_empty();
}
else {
ff = 1;
lst += X;
}
X = 0;
cnt = 0;
}
}
}
else {
if (cnt++ < 11) {
X = X * 2 + x;
if (cnt == 11) {
dis[X] = lst;
vis_cnt += 1;
for (auto [to, w] : g[X]) {
if (dis[to] > dis[X] + w) {
pq.emplace(-(dis[to] = dis[X] + w), to);
}
}
while (!empty(pq) && -pq.top().first != dis[pq.top().second]) {
pq.pop();
}
fix_pq_empty();
cnt = 0;
ff = 0;
X = 0;
}
}
}
}
