#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
#define add(x,y) ((((x)+(y))%md+md)%md)
#define Add(x,y) (x=add(x,y))
#define mul(x,y) ((((x)*(y))%md+md)%md)
#define Mul(x,y) (x=mul(x,y))
namespace {
template<class T> T chmn(T &x,T y){ return x=min(x,y); }
template<class T> T chmx(T &x,T y){ return x=max(x,y); }
const int inf=1e9;
const ll linf=1e18;
const ll md=1e9+7;
// const ll md=119<<23|1;
vector<pii> adj[2005];
priority_queue<pii,vector<pii>,greater<pii>> pq;
int d[2005],d0[2005];
vector<pii> tmp;
ll m,m0,cnt,n,w0;
void send(bool x){
return SendA(x);
}
void push(){
for(int i=0;i<n;++i) if(d[i]<d0[i]) tmp.eb(d0[i]=d[i], i);
}
void play(){
push();
int n=sz(tmp);
for(int i=0;i<11;++i) send(n&1), n>>=1;
for(auto [w,v]:tmp){
for(int i=0;i<20;++i) send(w&1), w>>=1;
for(int i=0;i<11;++i) send(v&1), v>>=1;
}
tmp.clear();
}
void dijk(){
while(!pq.empty()){
auto [w,u] = pq.top(); pq.pop();
if(d[u]!=w) continue;
for(auto &[v,vw]:adj[u]) if(d[v]>w+vw) pq.emplace(d[v]=w+vw,v);
}
}
} // namespace
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
n=N;
for(int i=0;i<A;++i) adj[U[i]].eb(V[i],C[i]), adj[V[i]].eb(U[i],C[i]);
m=m0=cnt=0;
fill(d,d+N,int(1e6));
fill(d0,d0+N,int(1e6));
pq.emplace(d[0]=0,0);
dijk();
play();
}
void ReceiveA(bool x) {
if(!m){
m0 |= x<<cnt;
if(++cnt==11){
m=m0, m0=cnt=0;
if(m==0){
dijk();
bool ok=0;
for(int i=0;!ok&&i<n;++i) if(d[i]<d0[i]) ok=1;
if(!ok) return;
play();
}
}
return;
}
if(cnt<20) m0 |= x<<cnt;
else m0 |= x<<cnt-20;
++cnt;
if(cnt==20) w0=m0, m0=0;
else if(cnt==31){
int w=w0, v=m0;
if(d[v]>w) pq.emplace(d[v]=d0[v]=w,v);
m0=cnt=0;
if(--m==0){
dijk();
play();
}
}
}
std::vector<int> Answer() {
vector<int> ans(n);
for(int i=0;i<n;++i) ans[i]=d[i];
return ans;
}
#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
#define add(x,y) ((((x)+(y))%md+md)%md)
#define Add(x,y) (x=add(x,y))
#define mul(x,y) ((((x)*(y))%md+md)%md)
#define Mul(x,y) (x=mul(x,y))
template<class T> T chmn(T &x,T y){ return x=min(x,y); }
template<class T> T chmx(T &x,T y){ return x=max(x,y); }
const int inf=1e9;
const ll linf=1e18;
const ll md=1e9+7;
// const ll md=119<<23|1;
namespace {
vector<pii> adj[2005];
priority_queue<pii,vector<pii>,greater<pii>> pq;
int d[2005],d0[2005];
vector<pii> tmp;
ll m,m0,cnt,n,w0;
void send(bool x){
return SendB(x);
}
void push(){
for(int i=0;i<n;++i) if(d[i]<d0[i]) tmp.eb(d0[i]=d[i], i);
}
void play(){
push();
int n=sz(tmp);
for(int i=0;i<11;++i) send(n&1), n>>=1;
for(auto &[w,v]:tmp){
for(int i=0;i<20;++i) send(w&1), w>>=1;
for(int i=0;i<11;++i) send(v&1), v>>=1;
}
tmp.clear();
}
void dijk(){
while(!pq.empty()){
auto [w,u] = pq.top(); pq.pop();
if(d[u]!=w) continue;
for(auto &[v,vw]:adj[u]) if(d[v]>w+vw) pq.emplace(d[v]=w+vw,v);
}
}
} // namespace
void InitB(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
n=N;
for(int i=0;i<A;++i) adj[U[i]].eb(V[i],C[i]), adj[V[i]].eb(U[i],C[i]);
m=m0=cnt=0;
fill(d,d+N,int(1e6));
fill(d0,d0+N,int(1e6));
pq.emplace(d[0]=0,0);
dijk();
}
void ReceiveB(bool x) {
if(!m){
m0 |= x<<cnt;
if(++cnt==11){
m=m0, m0=cnt=0;
if(m==0){
dijk();
bool ok=0;
for(int i=0;!ok&&i<n;++i) if(d[i]<d0[i]) ok=1;
if(!ok) return;
play();
}
}
return;
}
if(cnt<20) m0 |= x<<cnt;
else m0 |= x<<cnt-20;
++cnt;
if(cnt==20) w0=m0, m0=0;
else if(cnt==31){
int w=w0, v=m0;
if(d[v]>w) pq.emplace(d[v]=d0[v]=w,v);
m0=cnt=0;
if(--m==0){
dijk();
play();
}
}
}
