#include "Azer.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
static const int N = 2007, mxc = (1 << 9)-1, inf = 1e9;
static int n, m, ldis, str, x, y, w;
static set <pii> s;
static vector <pii> adj[N];
static vector <int> d;
static queue <int> bits;
void InitA(int nn, int aa, vector<int> uu, vector<int> vv, vector<int> cc) {
n = nn; m = aa;
for (int i = 0; i < m; i++) {
adj[uu[i]].pb({vv[i], cc[i]});
adj[vv[i]].pb({uu[i], cc[i]});
}
str = -1;
d.resize(n, inf);
d[0] = 0;
for (auto it : adj[0]) d[it.F] = it.S;
for (int i = 1; i < n; i++) s.insert({d[i], i});
}
void ReceiveA(bool x) {
if (str != -1) bits.push(x);
else str = 0;
auto snum = [&](int x, int si) {
for (int i = 0; i < si; i++) SendA((x>>i)&1);
};
auto rnum = [&](int si) {
int x = 0;
for (int i = 0; i < si; i++) {
x |= (int)bits.front() << i;
bits.pop();
}
return x;
};
if (str == 1 && bits.size() < 9) return;
if (str == 2 && bits.size() < 11) return;
if (!str) {
y = n, w = mxc;
for (auto it : s) {
if (it.F-ldis < w) {
w = it.F-ldis;
y = it.S;
}
}
snum(w, 9);
str = 1;
return;
}
else if (str == 1) {
int x = rnum(9);
if (x > w) snum(y, 11);
else {
str = 2;
return;
}
}
else {
y = rnum(11), w = x;
}
str = 0;
s.erase({d[y], y});
d[y] = (ldis += w);
for (auto it : adj[y]) {
if (d[y] + it.S < d[it.F]) {
s.erase({d[it.F], it.F});
d[it.F] = d[y]+it.S;
s.insert({d[it.F], it.F});
}
}
}
vector<int> Answer() {
return d;
}
#include "Baijan.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
static const int N = 2007, mxc = (1 << 9)-1, inf = 1e9;
static int n, m, ldis, str, x, y, w;
static set <pii> s;
static vector <pii> adj[N];
static vector <int> d;
static queue <int> bits;
void InitB(int nn, int bb, vector<int> ss, vector<int> tt, vector<int> dd) {
n = nn; m = bb;
for (int i = 0; i < m; i++) {
adj[ss[i]].pb({tt[i], dd[i]});
adj[tt[i]].pb({ss[i], dd[i]});
}
d.resize(n, inf);
d[0] = 0;
for (auto it : adj[0]) d[it.F] = it.S;
for (int i = 1; i < n; i++) s.insert({d[i], i});
SendB(1);
}
void ReceiveB(bool x) {
bits.push(x);
auto snum = [&](int x, int si) {
for (int i = 0; i < si; i++) SendB((x>>i)&1);
};
auto rnum = [&](int si) {
int x = 0;
for (int i = 0; i < si; i++) {
x |= (int)bits.front() << i;
bits.pop();
}
return x;
};
if (!str && bits.size() < 9) return;
if (str && bits.size() < 11) return;
if (!str) {
y = n, w = mxc;
for (auto it : s) {
if (it.F-ldis < w) {
w = it.F-ldis;
y = it.S;
}
}
x = rnum(9);
if (x >= w) {
snum(w, 9);
snum(y, 11);
}
else {
snum(w, 9);
str = 1;
return;
}
}
else {
y = rnum(11);
w = x;
}
str = 0;
s.erase({d[y], y});
d[y] = (ldis += w);
for (auto it : adj[y]) {
if (d[y] + it.S < d[it.F]) {
s.erase({d[it.F], it.F});
d[it.F] = d[y]+it.S;
s.insert({d[it.F], it.F});
}
}
}
