#include<bits/stdc++.h>
#include "Azer.h"
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N=2005;
namespace{
  int n,m,dis[N],vs[N],mx,val,lim=0,ps=0;
  vector<pair<int,int>>G[N];
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
  bool op;
  void send(int x,int op){ 
    if(!op){
      for(int i=0;i<9;i++)SendA(x>>i&1);
    }
    else{
      for(int i=0;i<11;i++)SendA(x>>i&1);
    }
  }
  //op=0:??????? 
  //op=1:?????? 
  void work(int u,int x){
  	assert(u<n);
    dis[u]=x,vs[u]=1;
    for(auto e:G[u]){
      if(dis[u]+e.se<dis[e.fi]){
        dis[e.fi]=dis[u]+e.se;
        q.push({dis[e.fi],e.fi});
      }
    }
  }
}

void InitA(int nn,int A,vector<int>U,vector<int>V,vector<int>C){
	n=nn,m=A;
	for(int i=0;i<m;i++){
		G[U[i]].pb({V[i],C[i]});
		G[V[i]].pb({U[i],C[i]});
	}
	memset(dis,0x3f,sizeof dis),dis[0]=0;
	send(0,0);
	q.push({0,0});
}
void ReceiveA(bool x){
	if(x)ps+=(1<<lim);
	lim++;
	if(!op){
		if(lim==9){
			//??????????? 
			if(!q.size()||q.top().fi>ps){
				val=ps+mx,op^=1;
			}
			//?????????????????????????? 
			else{
				send(q.top().se,1);
				work(q.top().se,q.top().fi);
				while(q.size()&&vs[q.top().se])q.pop();
				q.size()?send(q.top().fi-mx,0):send(501,0);
			}
			lim=ps=0;
		}
	}
	else{
		if(lim==11){
			work(ps,val);
			while(q.size()&&vs[q.top().se])q.pop();
			q.size()?send(q.top().fi-mx,0):send(501,0);
			op^=1,lim=ps=0;
		}
	}
	
}
vector<int>Answer(){
	vector<int>res;
	for(int i=0;i<n;i++)res.pb(dis[i]);
	return res;
}

#include<bits/stdc++.h>
#include "Baijan.h"
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N=2005;
namespace{
  int n,m,dis[N],vs[N],mx,val,lim=0,ps=0;
  vector<pair<int,int>>G[N];
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
  bool op;
  void send(int x,int op){ 
    if(!op){
      for(int i=0;i<9;i++)SendB(x>>i&1);
    }
    else{
      for(int i=0;i<11;i++)SendB(x>>i&1);
    }
  }
  //op=0:??????? 
  //op=1:?????? 
  void work(int u,int x){
  	assert(u<n);
    dis[u]=x,vs[u]=1;
    for(auto e:G[u]){
      if(dis[u]+e.se<dis[e.fi]){
        dis[e.fi]=dis[u]+e.se;
        q.push({dis[e.fi],e.fi});
      }
    }
  }
}
void InitB(int nn,int A,vector<int>U,vector<int>V,vector<int>C){
	n=nn,m=A;
	for(int i=0;i<m;i++){
		G[U[i]].pb({V[i],C[i]});
		G[V[i]].pb({U[i],C[i]});
	}
	memset(dis,0x3f,sizeof dis),dis[0]=0;
	send(0,0);
	q.push({0,0});
}
void ReceiveB(bool x){
	if(x)ps+=(1<<lim);
	lim++;
	if(!op){
		if(lim==9){
			//??????????? 
			if(!q.size()||q.top().fi>=ps){
				val=ps+mx,op^=1;
			}
			//?????????????????????????? 
			else{
				send(q.top().se,1);
				work(q.top().se,q.top().fi);
				while(q.size()&&vs[q.top().se])q.pop();
				q.size()?send(q.top().fi-mx,0):send(501,0);
			}
			lim=ps=0;
		}
	}
	else{
		if(lim==11){
			work(ps,val);
			while(q.size()&&vs[q.top().se])q.pop();
			q.size()?send(q.top().fi-mx,0):send(501,0);
			op^=1,lim=ps=0;
		}
	}
	
}