#include "Azer.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace {
int n;
int dist[58005];
vector<array<int,2>>g[58005];
priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>>pq;
int mxdist = 0;
string curdis = "";
string curloc = "";
int cn = 1;
} // namespace
void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
n = N;
for (int i = 0; i < A; ++i) {
g[U[i]].push_back({V[i],C[i]});
g[V[i]].push_back({U[i],C[i]});
}
fill(dist,dist+58005,1e9);
dist[0]=0;
for(array<int,2>a:g[0]){
pq.push({a[1],a[0]});
}
if(pq.size()){
int dis = pq.top()[0];
dis-=mxdist;
for(int i = 0;i<9;i++){
if((1<<i)&dis){
SendA(1);
}
else{
SendA(0);
}
}
}
else{
for(int i = 0;i<9;i++){
SendA(1);
}
}
}
void ReceiveA(bool x) {
while(pq.size()&&dist[pq.top()[1]]!=1e9){
pq.pop();
}
if(cn>=n)
return;
if(curdis.size()<9){
if(x){
curdis+="1";
}
else{
curdis+="0";
}
if(curdis.size()==9){
//just received entire dist
int curdist = 0;
for(int i = 0;i<9;i++){
if(curdis[i]=='1'){
curdist+=(1<<i);
}
}
cerr << "A received dist: " << curdist << "\n";
if(!(pq.size()==0)&&mxdist+curdist>=pq.top()[0]){
//must use current
array<int,2>a = pq.top();
pq.pop();
cerr << "A decides to send loc: " << a[1] << "\n";
for(int i = 0;i<11;i++){
if(a[1]&(1<<i)){
SendA(1);
}
else{
SendA(0);
}
}
dist[a[1]]=a[0];
cn++;
for(array<int,2>e:g[a[1]]){
pq.push({a[0]+e[1],e[0]});
}
mxdist=a[0];
while(pq.size()&&dist[pq.top()[1]]!=1e9){
pq.pop();
}
if(pq.size()){
int dis = pq.top()[0];
dis-=mxdist;
for(int i = 0;i<9;i++){
if((1<<i)&dis){
SendA(1);
}
else{
SendA(0);
}
}
}
else{
for(int i = 0;i<9;i++){
SendA(1);
}
}
curdis="";
}
}
}
else{
//new loc being received
if(curloc.size()<11){
if(x){
curloc+="1";
}
else{
curloc+="0";
}
}
if(curloc.size()==11){
int loc = 0;
for(int i = 0;i<11;i++){
if(curloc[i]=='1'){
loc+=(1<<i);
}
}
cerr << "A received loc: " << loc << "\n";
int curdist = 0;
for(int i = 0;i<9;i++){
if(curdis[i]=='1'){
curdist+=(1<<i);
}
}
cerr << "A already had dist: " << curdist << "\n";
array<int,2>a = {mxdist+curdist,loc};
dist[a[1]]=a[0];
cn++;
for(array<int,2>e:g[a[1]]){
pq.push({a[0]+e[1],e[0]});
}
mxdist=a[0];
while(pq.size()&&dist[pq.top()[1]]!=1e9){
pq.pop();
}
if(pq.size()){
int dis = pq.top()[0];
dis-=mxdist;
cerr << "A sends the dist: " << dis << " for " << pq.top()[1] << "\n";
for(int i = 0;i<9;i++){
if((1<<i)&dis){
SendA(1);
}
else{
SendA(0);
}
}
}
else{
cerr << "A sends infinite\n";
for(int i = 0;i<9;i++){
SendA(1);
}
}
curdis="";
curloc="";
}
}
}
vector<int> Answer() {
vector<int> ans(n);
for (int k = 0; k < n; ++k) {
ans[k] = dist[k];
}
return ans;
}
#include "Baijan.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace {
int n;
int dist[58005];
vector<array<int,2>>g[58005];
priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>>pq;
int mxdist = 0;
int cn = 1;
string curdis = "";
string curloc = "";
} // namespace
void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
n = N;
for (int i = 0; i < B; ++i) {
g[S[i]].push_back({T[i],D[i]});
g[T[i]].push_back({S[i],D[i]});
}
fill(dist,dist+58005,1e9);
dist[0]=0;
for(array<int,2>a:g[0]){
pq.push({a[1],a[0]});
}
if(pq.size()){
int dis = pq.top()[0];
dis-=mxdist;
for(int i = 0;i<9;i++){
if((1<<i)&dis){
SendB(1);
}
else{
SendB(0);
}
}
}
else{
for(int i = 0;i<9;i++){
SendB(1);
}
}
}
void ReceiveB(bool x) {
while(pq.size()&&dist[pq.top()[1]]!=1e9){
pq.pop();
}
if(cn>=n){
return;
}
if(curdis.size()<9){
if(x){
curdis+="1";
}
else{
curdis+="0";
}
if(curdis.size()==9){
//just received entire dist
int curdist = 0;
for(int i = 0;i<9;i++){
if(curdis[i]=='1'){
curdist+=(1<<i);
}
}
cerr << "B received dist: " << curdist << "\n";
if(!(pq.size()==0)&&mxdist+curdist>pq.top()[0]){
//must use current
array<int,2>a = pq.top();
pq.pop();
cerr << "B decides to send loc: " << a[1] << "\n";
for(int i = 0;i<11;i++){
if(a[1]&(1<<i)){
SendB(1);
}
else{
SendB(0);
}
}
dist[a[1]]=a[0];
cn++;
for(array<int,2>e:g[a[1]]){
pq.push({a[0]+e[1],e[0]});
}
mxdist=a[0];
while(pq.size()&&dist[pq.top()[1]]!=1e9){
pq.pop();
}
if(pq.size()){
int dis = pq.top()[0];
dis-=mxdist;
for(int i = 0;i<9;i++){
if((1<<i)&dis){
SendB(1);
}
else{
SendB(0);
}
}
}
else{
for(int i = 0;i<9;i++){
SendB(1);
}
}
curdis="";
}
}
}
else{
//new loc being received
if(curloc.size()<11){
if(x){
curloc+="1";
}
else{
curloc+="0";
}
}
if(curloc.size()==11){
int loc = 0;
for(int i = 0;i<11;i++){
if(curloc[i]=='1'){
loc+=(1<<i);
}
}
cerr << "B received loc: " << loc << "\n";
int curdist = 0;
for(int i = 0;i<9;i++){
if(curdis[i]=='1'){
curdist+=(1<<i);
}
}
cerr << "B already had dist: " << curdist << "\n";
array<int,2>a = {mxdist+curdist,loc};
dist[a[1]]=a[0];
cn++;
for(array<int,2>e:g[a[1]]){
pq.push({a[0]+e[1],e[0]});
}
mxdist=a[0];
while(pq.size()&&dist[pq.top()[1]]!=1e9){
pq.pop();
}
if(pq.size()){
int dis = pq.top()[0];
dis-=mxdist;
cerr << "B sends the dist: " << dis << " for " << pq.top()[1] << "\n";
for(int i = 0;i<9;i++){
if((1<<i)&dis){
SendB(1);
}
else{
SendB(0);
}
}
}
else{
cerr << "B sends infinite\n";
for(int i = 0;i<9;i++){
SendB(1);
}
}
curdis="";
curloc="";
}
}
}
