#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;
vec<bool> vis;
priority_queue<pair<int, int>> pq;
vec<vec<pair<int, int>>> g;
void send_number(int x, int b) {
assert(x >= 0);
for (int i = b - 1; i >= 0; i--) {
SendA((x >> i) & 1);
}
}
void send_dis() {
if (vis_cnt == N) {
return;
}
while (!empty(pq) && vis[pq.top().second]) {
pq.pop();
}
if (empty(pq)) {
send_number((1 << 9) - 1, 9);
}
else {
send_number(-pq.top().first - lst, 9);
}
}
void relax(int i) {
for (auto [to, w] : g[i]) {
if (dis[to] > dis[i] + w) {
pq.emplace(-(dis[to] = dis[i] + w), to);
}
}
}
}
void InitA(int N, int A, vec<int> U, vec<int> V, vec<int> C) {
::N = N;
g.resize(N);
dis.resize(N, infty<int>);
vis.resize(N, false);
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[0] = true;
vis_cnt = 1;
relax(0);
send_dis();
}
void ReceiveA(bool f) {
if (ff == 0) {
if (cnt++ < 9) {
X = X * 2 + f;
if (cnt == 9) {
if (!empty(pq) && -pq.top().first - lst <= X) {
auto [d, i] = pq.top();
d = -d;
lst = d;
pq.pop();
vis[i] = true;
vis_cnt += 1;
relax(i);
send_number(i, 11);
send_dis();
}
else {
ff = 1;
lst += X;
}
cnt = 0;
X = 0;
}
}
}
else {
if (cnt++ < 11) {
X = X * 2 + f;
if (cnt == 11) {
dis[X] = lst;
vis[X] = true;
vis_cnt += 1;
relax(X);
send_dis();
ff = 0;
cnt = 0;
X = 0;
}
}
}
}
std::vector<int> Answer() {
return dis;
}
#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;
vec<bool> vis;
priority_queue<pair<int, int>> pq;
vec<vec<pair<int, int>>> g;
void send_number(int x, int b) {
assert(x >= 0);
for (int i = b - 1; i >= 0; i--) {
SendB((x >> i) & 1);
}
}
void send_dis() {
if (vis_cnt == N) {
return;
}
while (!empty(pq) && vis[pq.top().second]) {
pq.pop();
}
if (empty(pq)) {
send_number((1 << 9) - 1, 9);
}
else {
send_number(-pq.top().first - lst, 9);
}
}
void relax(int i) {
for (auto [to, w] : g[i]) {
if (dis[to] > dis[i] + w) {
pq.emplace(-(dis[to] = dis[i] + w), to);
}
}
}
}
void InitB(int N, int A, vec<int> U, vec<int> V, vec<int> C) {
::N = N;
g.resize(N);
dis.resize(N, infty<int>);
vis.resize(N, false);
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[0] = true;
vis_cnt = 1;
relax(0);
send_dis();
}
void ReceiveB(bool f) {
if (ff == 0) {
if (cnt++ < 9) {
X = X * 2 + f;
if (cnt == 9) {
if (!empty(pq) && -pq.top().first - lst < X) {
auto [d, i] = pq.top();
d = -d;
lst = d;
pq.pop();
vis[i] = true;
vis_cnt += 1;
relax(i);
send_number(i, 11);
send_dis();
}
else {
ff = 1;
lst += X;
}
cnt = 0;
X = 0;
}
}
}
else {
if (cnt++ < 11) {
X = X * 2 + f;
if (cnt == 11) {
dis[X] = lst;
vis[X] = true;
vis_cnt += 1;
relax(X);
send_dis();
ff = 0;
cnt = 0;
X = 0;
}
}
}
}
