#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
typedef long long ll;
const int N = 2000;
const int INF = 1'000'100;
const int M = 20;
int n, m, mark[N + 10], ans[N + 10];
vector<pair<int, int>> adj[N + 10];
set<pair<int, int>> s;
int dis[N + 10];
mt19937 rng(123);
int bl, readDis, lastDist, type;
vector<int> detail, vecDis;
void readInput(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
n = N;
m = A;
for (int i = 0; i < m; i++) {
int u = U[i], v = V[i], c = C[i];
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
}
void checkDis(int u) {
for (auto [v, w]: adj[u])
if (dis[u] + w < dis[v]) {
s.erase({dis[v], v});
dis[v] = dis[u] + w;
s.insert({dis[v], v});
}
}
void init() {
for (int i = 1; i < n; i++) {
mark[i] = 0;
dis[i] = INF;
s.insert({dis[i], i});
}
dis[0] = 0;
mark[0] = true;
checkDis(0);
}
void outputInt(int x, int M) {
for (int j = M - 1; j >= 0; j--) {
int bit = ((x & (1 << j))? 1: 0);
SendA(bit);
}
}
void outputDis(int x) {
outputInt(x, M);
}
void outputVer(int x) {
outputInt(x, 11);
}
void addVer(int u) {
mark[u] = true;
s.erase({dis[u], u});
ans[u] = dis[u];
checkDis(u);
}
bool isA() {
return false;//rng() % 2 == 0;
}
void step() {
if (!isA()) {
type = 2;
readDis = true;
return;
}
bool is = false;
for (int i = 0; i < n; i++)
if (mark[i] == false)
is = true;
if (!is)
return;
type = 1;
bl = true;
outputDis(s.begin() -> first);
}
void newGood(int u, int dist) {
s.erase({dis[u], u});
dis[u] = dist;
addVer(u);
}
int calcDis() {
int res = 0;
for (int i = 0; i < 20; i++)
res = res * 2 + vecDis[i];
vecDis.clear();
return res;
}
int calcVer() {
int res = 0;
for (int i = 0; i < 11; i++)
res = res * 2 + detail[i];
detail.clear();
return res;
}
void checkDetail() {
int dist = 0, u = 0;
for (int i = 0; i < 20; i++)
dist = dist * 2 + detail[i];
for (int i = 20; i < 31; i++)
u = u * 2 + detail[i];
detail.clear();
newGood(u, dist);
}
void ReceiveA2(bool x) {
/*if (readDis) {
vecDis.push_back(x);
if (vecDis.size() == 20) {
readDis = false;
int dist = calcDis();
if (s.begin() -> first < dist) {
SendA(1);
outputDis(s.begin() -> first);
outputVer(s.begin() -> second);
addVer(s.begin() -> second);
step();
}
else {
lastDist = dist;
SendA(0);
}
}
}
else {*/
vecDis.push_back(x);
if (detail.size() == 11) {
int u = calcVer();
newGood(u, lastDist);
step();
}
//}
}
}
void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
readInput(N, A, U, V, C);
init();
type = 0;
for (int i = 0; i < n; i++) {
SendA(0);
//cout << vecDis.size() << endl;
//int dist = calcDis();
//ans[i] = dist;
}
//step();
}
void ReceiveA(bool x) {
/*if (type == 2) {
ReceiveA2(x);
return;
}
if (bl) {
bl = false;
if (x == 0) {
outputVer(s.begin() -> second);
addVer(s.begin() -> second);
step();
}
}
else {*/
vecDis.push_back(x);
if (vecDis.size() == 20) {
int dist = calcDis();
ans[type++] = dist;
}
//}
}
vector<int> Answer() {
vector<int> res;
for (int i = 0; i < n; i++)
res.push_back(ans[i]);
return res;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
typedef long long ll;
const int N = 2000;
const int INF = 1'000'100;
const int M = 20;
int n, m, mark[N + 10], ans[N + 10];
vector<pair<int, int>> adj[N + 10];
set<pair<int, int>> s;
int dis[N + 10];
mt19937 rng(123);
int bl, readDis, lastDist, type;
vector<int> detail, vecDis;
void readInput(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
n = N;
m = A;
for (int i = 0; i < m; i++) {
int u = U[i], v = V[i], c = C[i];
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
}
void checkDis(int u) {
for (auto [v, w]: adj[u])
if (dis[u] + w < dis[v]) {
s.erase({dis[v], v});
dis[v] = dis[u] + w;
s.insert({dis[v], v});
}
}
void init() {
for (int i = 1; i < n; i++) {
dis[i] = INF;
s.insert({dis[i], i});
mark[i] = 0;
}
dis[0] = 0;
mark[0] = true;
checkDis(0);
}
void outputInt(int x, int M) {
for (int j = M - 1; j >= 0; j--) {
int bit = ((x & (1 << j))? 1: 0);
SendB(bit);
}
}
void outputDis(int x) {
outputInt(x, M);
}
void outputVer(int x) {
outputInt(x, 11);
}
bool isB() {
return rng() % 2 == 1;
}
void step() {
if (!isB()) {
type = 2;
readDis = true;
return;
}
bool is = false;
for (int i = 0; i < n; i++)
if (mark[i] == false)
is = true;
if (!is)
return;
type = 1;
bl = true;
outputDis(s.begin() -> first);
}
void addVer(int u) {
mark[u] = true;
s.erase({dis[u], u});
ans[u] = dis[u];
checkDis(u);
}
void newGood(int u, int dist) {
s.erase({dis[u], u});
dis[u] = dist;
addVer(u);
}
int calcDis() {
int res = 0;
for (int i = 0; i < 20; i++)
res = res * 2 + vecDis[i];
vecDis.clear();
return res;
}
int calcVer() {
int res = 0;
for (int i = 0; i < 11; i++)
res = res * 2 + detail[i];
detail.clear();
return res;
}
void checkDetail() {
int dist = 0, u = 0;
for (int i = 0; i < 20; i++)
dist = dist * 2 + detail[i];
for (int i = 20; i < 31; i++)
u = u * 2 + detail[i];
detail.clear();
newGood(u, dist);
}
void ReceiveB2(bool x) {
if (readDis) {
vecDis.push_back(x);
if (vecDis.size() == 20) {
readDis = false;
int dist = calcDis();
if (s.begin() -> first < dist) {
SendB(1);
outputDis(s.begin() -> first);
outputVer(s.begin() -> second);
addVer(s.begin() -> second);
step();
}
else {
lastDist = dist;
SendB(0);
}
}
}
else {
detail.push_back(x);
if (detail.size() == 11) {
int u = calcVer();
newGood(u, lastDist);
step();
}
}
}
void calcAll() {
s.insert({0, 0});
while (!s.empty()) {
int u = s.begin() -> second;
addVer(u);
}
}
}
void InitB(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
readInput(N, A, U, V, C);
init();
calcAll();
//step();
type = 0;
}
void ReceiveB(bool x) {
outputDis(dis[type]);
type++;
/*if (type == 2) {
ReceiveB2(x);
return;
}
if (bl) {
bl = false;
if (x == 0) {
outputVer(s.begin() -> second);
addVer(s.begin() -> second);
step();
}
}
else {
detail.push_back(x);
if (detail.size() == 31) {
checkDetail();
step();
}
}*/
}
