#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long
namespace {
constexpr int maxN=2e3+5;
int n,dis[maxN],lstdis,nowdis,len,type,val,determined;
// type 1 : dis
// type 2 : idx
vector<pair<int,int>> adj[maxN];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
inline void sendIdx(int v){
//cout<<"A send idx "<<v<<'\n';
for(int i = 11;i--;)SendA(v>>i&1);
}
inline void sendDis(int v){
//cout<<"A send dist "<<v<<'\n';
for(int i = 9;i--;)SendA(v>>i&1);
}
inline void push1(){
for(int cnt = 1;!pq.empty();){
auto [d,u] = pq.top();
if(d!=dis[u]){
pq.pop();
continue;
}
if(!cnt){
nowdis = d;
sendDis(d-lstdis);
val = 0;
type = 1;
len = 0;
return;
}
pq.pop();
cnt--;
determined++;
for(auto [v,c]:adj[u])if(dis[v]>dis[u]+c)pq.emplace(dis[v]=dis[u]+c,v);
}
if(determined==n)return;
nowdis = 511+lstdis;
sendDis(511);
val = 0;
type = 1;
len = 0;
}
}
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]].emplace_back(V[i],C[i]);
adj[V[i]].emplace_back(U[i],C[i]);
}
fill(dis,dis+n,1e9);
pq.emplace(dis[0] = 0,0);
push1();
}
void ReceiveA(bool x) {
len++;
val<<=1;
val|=x;
if(type==1){
if(len==9){
//cout<<"A receives dist "<<val<<'\n';
if(nowdis>=val+lstdis){
lstdis += val;
val = 0;
type = 2;
len = 0;
return;
}
lstdis = nowdis;
sendIdx(pq.top().second);
push1();
}
}
else {
if(len==11){
//cout<<"A receives index "<<val<<"\n";
pq.emplace(dis[val] = lstdis,val);
push1();
}
}
}
std::vector<int> Answer() {
vector<int> res(n);
for(int i = 0;i<n;i++)res[i] = dis[i];
return res;
}
#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long
namespace {
constexpr int maxN=2e3+5;
int n,dis[maxN],lstdis,nowdis,len,type,val,determined;
// type 1 : dis
// type 2 : idx
vector<pair<int,int>> adj[maxN];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
inline void sendIdx(int v){
//cout<<"B send idx "<<v<<'\n';
for(int i = 11;i--;)SendB(v>>i&1);
}
inline void sendDis(int v){
//cout<<"B send dist "<<v<<'\n';
for(int i = 9;i--;)SendB(v>>i&1);
}
inline void push1(){
for(int cnt = 1;!pq.empty();){
auto [d,u] = pq.top();
if(d!=dis[u]){
pq.pop();
continue;
}
if(!cnt){
nowdis = d;
sendDis(d-lstdis);
val = 0;
type = 1;
len = 0;
return;
}
pq.pop();
cnt--;
determined++;
for(auto [v,c]:adj[u])if(dis[v]>dis[u]+c)pq.emplace(dis[v]=dis[u]+c,v);
}
if(determined==n)return;
nowdis = 511+lstdis;
sendDis(511);
val = 0;
type = 1;
len = 0;
}
}
void InitB(int N, int B, std::vector<int> U, std::vector<int> V,std::vector<int> C) {
n=N;
for(int i = 0;i<B;i++){
adj[U[i]].emplace_back(V[i],C[i]);
adj[V[i]].emplace_back(U[i],C[i]);
}
fill(dis,dis+n,1e9);
pq.emplace(dis[0] = 0,0);
push1();
}
void ReceiveB(bool x) {
len++;
val<<=1;
val|=x;
if(type==1){
if(len==9){
//cout<<"B receives dist "<<val<<'\n';
if(nowdis>val+lstdis){
lstdis += val;
val = 0;
type = 2;
len = 0;
return;
}
lstdis = nowdis;
sendIdx(pq.top().second);
push1();
}
}
else {
if(len==11){
//cout<<"B receives index "<<val<<"\n";
pq.emplace(dis[val] = lstdis,val);
push1();
}
}
}
