#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int nx=2e3+5, inf=1e9, kx=9;
mt19937 rng(12345678);
enum MODE {WAIT, SENDER_FIRST, SENDER_WAIT, SENDER_SECOND, RECIEVER_FIRST, RECIEVER_SECOND};
MODE mode;
int n, cur, mn[nx], vs[nx], mx, w, u, randm[nx], saved;
vector<pair<int, int>> d[nx];
vector<int> in;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
void sendtop()
{
while (!pq.empty()&&vs[pq.top().second]) pq.pop();
//cout<<"send top "<<pq.top().first<<' '<<pq.top().second<<'\n';
if (pq.empty()) for (int i=0; i<kx; i++) SendA(1);
else
{
auto [w, u]=pq.top();
for (int i=0; i<kx; i++) SendA((w-mx)&(1<<i));
}
}
void sendnum()
{
for (int i=0; i<11; i++) SendA(pq.top().second&(1<<i));
}
void update(int w, int u)
{
//cout<<"update A "<<w<<' '<<u<<'\n';
cur++;
mn[u]=mx=w, vs[u]=1;
for (auto [v, cw]:d[u]) if (mn[v]>w+cw) mn[v]=w+cw, pq.push({mn[v], v});
}
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
n=N;
cur=1;
for (int i=1; i<N; i++) mn[i]=inf;
for (int i=0; i<A; i++) d[U[i]].push_back({V[i], C[i]}), d[V[i]].push_back({U[i], C[i]});
for (int i=1; i<=N; i++) randm[i]=rng()%2; //cout<<"randm A "<<randm[i]<<'\n';
pq.push({0, 0});
mode=WAIT;
if (randm[cur]) SendA(1);
}
void ReceiveA(bool x) {
//cout<<"mode a "<<mode<<' '<<x<<'\n';
if (mode==WAIT)
{
if (x==1) SendA(0), mode=SENDER_FIRST, ReceiveA(0);
else mode=RECIEVER_FIRST;
}
else if (mode==SENDER_FIRST)
{
sendtop();
mode=SENDER_WAIT;
}
else if (mode==SENDER_WAIT)
{
if (x==1) mode=SENDER_SECOND;
else
{
update(pq.top().first, pq.top().second);
sendnum();
if (cur>n) return;
mode=WAIT;
if (randm[cur]) SendA(1);
}
}
else if (mode==SENDER_SECOND)
{
in.push_back(x);
if (in.size()<20) return;
u=0, w=0;
for (int i=0; i<11; i++) u|=in[i]<<i;
for (int i=0; i<kx; i++) w|=in[i+11]<<i;
in.clear();
w=mx+w;
update(w, u);
if (cur>n) return;
mode=WAIT;
if (randm[cur]) SendA(1);
}
else if (mode==RECIEVER_FIRST)
{
in.push_back(x);
if (in.size()<kx) return;
w=0;
for (int i=0; i<kx; i++) w|=(in[i]<<i);
w=mx+w;
in.clear();
while (!pq.empty()&&vs[pq.top().second]) pq.pop();
int cw=INT_MAX;
if (!pq.empty()) cw=pq.top().first;
if (w<=cw)
{
SendA(0);
saved=w;
mode=RECIEVER_SECOND;
}
else
{
SendA(1);
sendnum();
sendtop();
update(pq.top().first, pq.top().second);
if (cur>n) return;
mode=WAIT;
if (randm[cur]) SendA(1);
}
}
else if (mode==RECIEVER_SECOND)
{
in.push_back(x);
if (in.size()<11) return;
u=0;
for (int i=0; i<11; i++) u|=(in[i]<<i);
in.clear();
update(saved, u);
if (cur>n) return;
mode=WAIT;
if (randm[cur]) SendA(1);
}
}
std::vector<int> Answer() {
std::vector<int> ans(n);
for (int i=0; i<n; i++) ans[i]=mn[i];
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int nx=2e3+5, inf=1e9, kx=9;
mt19937 rng(12345678);
enum MODE {WAIT, SENDER_FIRST, SENDER_WAIT, SENDER_SECOND, RECIEVER_FIRST, RECIEVER_SECOND};
MODE mode;
int n, cur, mn[nx], vs[nx], mx, w, u, randm[nx], saved;
vector<pair<int, int>> d[nx];
vector<int> in;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
void sendtop()
{
while (!pq.empty()&&vs[pq.top().second]) pq.pop();
if (pq.empty()) for (int i=0; i<kx; i++) SendB(1);
else
{
auto [w, u]=pq.top();
for (int i=0; i<kx; i++) SendB((w-mx)&(1<<i));
}
}
void sendnum()
{
for (int i=0; i<11; i++) SendB(pq.top().second&(1<<i));
}
void update(int w, int u)
{
//cout<<"update B "<<w<<' '<<u<<'\n';
cur++;
mn[u]=mx=w, vs[u]=1;
for (auto [v, cw]:d[u]) if (mn[v]>w+cw) mn[v]=w+cw, pq.push({mn[v], v});
}
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
std::vector<int> D) {
n=N;
cur=1;
for (int i=1; i<N; i++) mn[i]=inf;
for (int i=0; i<B; i++) d[S[i]].push_back({T[i], D[i]}), d[T[i]].push_back({S[i], D[i]});
for (int i=1; i<=N; i++) randm[i]=!(rng()%2); //cout<<"randm B "<<randm[i]<<'\n';
pq.push({0, 0});
mode=WAIT;
if (randm[cur]) SendB(1);
}
void ReceiveB(bool y) {
//cout<<"mode b "<<mode<<' '<<y<<'\n';
if (mode==WAIT)
{
if (y==1) SendB(0), mode=SENDER_FIRST, ReceiveB(0);
else mode=RECIEVER_FIRST;
}
else if (mode==SENDER_FIRST)
{
sendtop();
mode=SENDER_WAIT;
}
else if (mode==SENDER_WAIT)
{
if (y==1) mode=SENDER_SECOND;
else
{
update(pq.top().first, pq.top().second);
sendnum();
if (cur>n) return;
mode=WAIT;
if (randm[cur]) SendB(1);
}
}
else if (mode==SENDER_SECOND)
{
in.push_back(y);
if (in.size()<20) return;
u=0, w=0;
for (int i=0; i<11; i++) u|=in[i]<<i;
for (int i=0; i<kx; i++) w|=in[i+11]<<i;
in.clear();
w=mx+w;
update(w, u);
if (cur>n) return;
mode=WAIT;
if (randm[cur]) SendB(1);
}
else if (mode==RECIEVER_FIRST)
{
in.push_back(y);
if (in.size()<kx) return;
w=0;
for (int i=0; i<kx; i++) w|=(in[i]<<i);
w=mx+w;
in.clear();
while (!pq.empty()&&vs[pq.top().second]) pq.pop();
int cw=INT_MAX;
if (!pq.empty()) cw=pq.top().first;
if (w<=cw)
{
SendB(0);
saved=w;
mode=RECIEVER_SECOND;
}
else
{
SendB(1);
sendnum();
sendtop();
update(pq.top().first, pq.top().second);
if (cur>n) return;
mode=WAIT;
if (randm[cur]) SendB(1);
}
}
else if (mode==RECIEVER_SECOND)
{
in.push_back(y);
if (in.size()<11) return;
u=0;
for (int i=0; i<11; i++) u|=(in[i]<<i);
in.clear();
update(saved, u);
if (cur>n) return;
mode=WAIT;
if (randm[cur]) SendB(1);
}
}
