#include <bits/stdc++.h>
#include "Azer.h"
/*
*/
namespace{
int state=0,nbits=0,result=0;//Comparing, Receiving Location
int curdist=0;
int othdist=0,othnum=0;
int nrounds=0;
std::vector<int> dists;
std::vector<std::vector<std::pair<int,int>>> edges;
std::priority_queue<std::pair<int,int>> distspq;
int n;
void upddists(int vert,int dist){
dists[vert]=dist;
for(std::pair<int,int> i:edges[vert]){
distspq.push({-(dist+i.second),i.first});
}
}
void senddist(){
if(nrounds++==n-1)return;
state=0;
while(!distspq.empty()&&dists[distspq.top().second]!=1e9){
distspq.pop();
}
std::pair<int,int> topdist=distspq.empty()?std::pair<int,int>(-1e9,-1):distspq.top();
int val=(-topdist.first)==1e9?511:-topdist.first-curdist;
//std::cout<<"A sends "<<val<<'\n';
for(int i=0;i<9;i++){
SendA((val>>i)&1);
}
}
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C){
n=N;
edges.clear();
edges.resize(N);
for(int i=0;i<A;i++){
edges[U[i]].push_back({V[i],C[i]});
edges[V[i]].push_back({U[i],C[i]});
}
dists.clear();
dists.resize(N,1e9);
upddists(0,0);
senddist();
}
void ReceiveA(bool x){
result+=(1<<(nbits++))*x;
if(state==0&&nbits==9){
othdist=result==511?1e9:result+curdist;
//std::cout<<othdist<<" othdist\n";
std::pair<int,int> topdist=distspq.empty()?std::pair<int,int>(-1e9,-1):distspq.top();
int curldist=-topdist.first;
if(othdist<curldist){
//std::cout<<"B to send r"<<nrounds<<'\n';
state=1;//they send the new vertex
nbits=0;
}else{
int val=topdist.second;
//std::cout<<"A sends vertex "<<val<<" r"<<nrounds<<'\n';
for(int i=0;i<11;i++){
SendA((val>>i)&1);
}
upddists(val,curldist);
curdist=curldist;
senddist();
}
result=0;
nbits=0;
}else if(state==1&&nbits==11){
upddists(result,othdist);
curdist=othdist;
result=0;
nbits=0;
senddist();
}
}
std::vector<int> Answer(){
return dists;
}
#include <bits/stdc++.h>
#include "Baijan.h"
/*
*/
namespace{
int state=0,nbits=0,result=0;//Comparing, Receiving Location
int curdist=0;
int othdist=0,othnum=0;
int nrounds=0;
std::vector<int> dists;
std::vector<std::vector<std::pair<int,int>>> edges;
std::priority_queue<std::pair<int,int>> distspq;
int n;
void upddists(int vert,int dist){
dists[vert]=dist;
for(std::pair<int,int> i:edges[vert]){
distspq.push({-(dist+i.second),i.first});
}
}
void senddist(){
if(nrounds++==n-1)return;
state=0;
while(!distspq.empty()&&dists[distspq.top().second]!=1e9){
distspq.pop();
}
std::pair<int,int> topdist=distspq.empty()?std::pair<int,int>(-1e9,-1):distspq.top();
int val=(-topdist.first)==1e9?511:-topdist.first-curdist;
//std::cout<<"B sends "<<val<<'\n';
for(int i=0;i<9;i++){
SendB((val>>i)&1);
}
}
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D){
n=N;
edges.clear();
edges.resize(N);
for(int i=0;i<B;i++){
edges[S[i]].push_back({T[i],D[i]});
edges[T[i]].push_back({S[i],D[i]});
}
dists.clear();
dists.resize(N,1e9);
upddists(0,0);
senddist();
}
void ReceiveB(bool x){
result+=(1<<(nbits++))*x;
if(state==0&&nbits==9){
othdist=result==511?1e9:result+curdist;
std::pair<int,int> topdist=distspq.empty()?std::pair<int,int>(-1e9,-1):distspq.top();
int curldist=-topdist.first;
if(curldist<othdist){
int val=topdist.second;
//std::cout<<"B sends vertex "<<val<<" r"<<nrounds<<'\n';
for(int i=0;i<11;i++){
SendB((val>>i)&1);
}
upddists(val,curldist);
curdist=curldist;
senddist();
}else{
//std::cout<<"A to send r"<<nrounds<<'\n';
state=1;//they send the new vertex
}
result=0;
nbits=0;
}else if(state==1&&nbits==11){
upddists(result,othdist);
curdist=othdist;
result=0;
nbits=0;
senddist();
}
}
