#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace {
const int maxn = 2005, INF = 1e10;
int n, m, remain;
vector<pair<int, int>> adj[maxn];
int dist[maxn];
int mx;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int lg(int x) {
if (x == 0) return 0;
else return log2(x);
}
void sendid(int id) {
// cout << "Asendid " << id << endl;
int val = -1;
for (int i=0;i<=id;i++) val += (dist[i] == INF);
// cout << val << endl;
int sz = lg(remain-1) + 1;
for (int i=0;i<sz;i++) {
SendA(val & (1<<i));
// cout << (bool)(val & (1<<i));
}
// cout << endl;
}
void sendval(int val) {
// cout << "Asendval " << val << endl;
for (int i=0;i<9;i++) {
SendA((val-mx) & (1<<i));
// cout << (bool)((val-mx) & (1<<i));
}
// cout << endl;
}
void firm(int u, int d) {
// cout << "Afirm " << u << " " << d << endl;
dist[u] = d;
mx = max(d, mx);
for (auto [v, w]:adj[u]) if (dist[v] == INF) pq.push({d + w, v});
remain--;
// cout << remain << endl;
}
void takemine(int u, int d, bool needsend) {
// cout << "Atakemine " << u << " " << d << endl;
SendA(0);
sendid(u);
if (needsend) sendval(d);
firm(u, d);
while (pq.size() > 0 && dist[pq.top().second] != INF) pq.pop();
int ask = 501 + mx;
if (pq.size() > 0) ask = pq.top().first;
sendval(ask);
}
int charsleft;
vector<bool> vec;
int fixid(int id) {
int cnt = -1;
for (int i=0;i<n;i++) {
cnt += (dist[i] == INF);
if (cnt == id) return i;
}
return 69420;
}
int nxtfirmval;
void received() {
int sz = lg(remain-1) + 1;
int u = 0;
for (int i=0;i<sz;i++) u += vec[i] * (1<<i);
u = fixid(u);
int firmval, ask;
if (nxtfirmval == -1) {
firmval = mx;
for (int i=0;i<9;i++) firmval += vec[i + sz] * (1<<i);
firm(u, firmval);
if (remain == 0) return;
ask = mx;
for (int i=0;i<9;i++) ask += vec[i + sz + 9] * (1<<i);
} else {
firmval = nxtfirmval;
firm(u, firmval);
if (remain == 0) return;
ask = mx;
for (int i=0;i<9;i++) ask += vec[i + sz] * (1<<i);
nxtfirmval = -1;
}
// cout << "Areceived " << u << " " << firmval << " " << ask << endl;
while (pq.size() > 0 && dist[pq.top().second] != INF) pq.pop();
if (pq.size() > 0 && pq.top().first < ask) {
u = pq.top().second;
int d = pq.top().first;
pq.pop();
takemine(u, d, 1);
} else {
SendA(1);
nxtfirmval = ask;
}
vec.clear();
}
} // namespace
void InitA(int32_t N, int32_t M, vector<int32_t> U, vector<int32_t> V,
vector<int32_t> W) {
n = N, m = M, mx = 0;
remain = n;
charsleft = 0;
nxtfirmval = -1;
vec.clear();
while (pq.size()) pq.pop();
for (int i=0;i<n;i++) adj[i].clear();
for (int i=0;i<n;i++) dist[i] = INF;
for (int i=0;i<m;i++) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
takemine(0, 0, 1);
}
void ReceiveA(bool x) {
// cout << 'A' << x << "\n";
if (charsleft) {
vec.push_back(x);
charsleft--;
if (!charsleft) {
received();
}
return;
}
if (x == 0) {
charsleft = lg(remain-1) + 1 + 9 + 9;
if (nxtfirmval != -1) charsleft -= 9;
return;
}
//take
int u = pq.top().second, d = pq.top().first;
pq.pop();
takemine(u, d, 0);
}
vector<int32_t> Answer() {
vector<int32_t> ans(n);
for (int i=0;i<n;i++) ans[i] = dist[i];
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace {
const int maxn = 2005, INF = 1e10;
int n, m, remain;
vector<pair<int, int>> adj[maxn];
int dist[maxn];
int mx;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int lg(int x) {
if (x == 0) return 0;
else return log2(x);
}
void firm(int u, int d) {
// cout << "Bfirm " << u << " " << d << endl;
dist[u] = d;
mx = max(d, mx);
for (auto [v, w]:adj[u]) if (dist[v] == INF) pq.push({d + w, v});
remain--;
// cout << remain << endl;
}
void sendid(int id) {
// cout << "Bsendid " << id << endl;
int val = -1;
for (int i=0;i<=id;i++) val += (dist[i] == INF);
int sz = lg(remain-1) + 1;
for (int i=0;i<sz;i++) SendB(val & (1<<i));
}
void sendval(int val) {
// cout << "Bsendval " << val << endl;
for (int i=0;i<9;i++) SendB((val-mx) & (1<<i));
}
void takemine(int u, int d, bool needsend) {
SendB(0);
sendid(u);
if (needsend) sendval(d);
firm(u, d);
while (pq.size() > 0 && dist[pq.top().second] != INF) pq.pop();
int ask = 501 + mx;
if (pq.size() > 0) ask = pq.top().first;
sendval(ask);
}
int charsleft;
vector<bool> vec;
int fixid(int id) {
int cnt = -1;
for (int i=0;i<n;i++) {
cnt += (dist[i] == INF);
if (cnt == id) return i;
}
return 69420;
}
int nxtfirmval;
void received() {
// for (bool i:vec) cout << i; cout << endl;
int sz = lg(remain-1) + 1;
int u = 0;
for (int i=0;i<sz;i++) u += vec[i] * (1<<i);
u = fixid(u);
int firmval, ask;
if (nxtfirmval == -1) {
firmval = mx;
for (int i=0;i<9;i++) firmval += vec[i + sz] * (1<<i);
firm(u, firmval);
if (remain == 0) return;
ask = mx;
for (int i=0;i<9;i++) ask += vec[i + sz + 9] * (1<<i);
} else {
firmval = nxtfirmval;
firm(u, firmval);
if (remain == 0) return;
ask = mx;
for (int i=0;i<9;i++) ask += vec[i + sz] * (1<<i);
nxtfirmval = -1;
}
// cout << "Brecieved " << u << " " << firmval << " " << ask << endl;
// cout << ask << endl;
while (pq.size() > 0 && dist[pq.top().second] != INF) pq.pop();
if (pq.size() > 0 && pq.top().first < ask) {
u = pq.top().second;
int d = pq.top().first;
pq.pop();
takemine(u, d, 1);
} else {
SendB(1);
nxtfirmval = ask;
}
vec.clear();
}
} // namespace
void InitB(int32_t N, int32_t M, vector<int32_t> U, vector<int32_t> V,
vector<int32_t> W) {
n = N, m = M, mx = 0;
remain = n;
charsleft = 0;
nxtfirmval = -1;
vec.clear();
while (pq.size()) pq.pop();
for (int i=0;i<n;i++) dist[i] = INF;
for (int i=0;i<n;i++) adj[i].clear();
for (int i=0;i<m;i++) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
}
void ReceiveB(bool x) {
// cout << 'B' << x << " " << charsleft << "\n";
if (charsleft) {
vec.push_back(x);
charsleft--;
if (!charsleft) {
received();
}
return;
}
if (x == 0) {
charsleft = lg(remain-1) + 1 + 9 + 9;
if (nxtfirmval != -1) charsleft -= 9;
return;
}
//take
int u = pq.top().second, d = pq.top().first;
pq.pop();
takemine(u, d, 0);
}
