#include<bits/stdc++.h>
#include "Azer.h"

using namespace std;
struct edge{
	int obj;
	int last;
	int val;
}e[1000006];
int head[2005],g;
vector<int>dist; 
void link(int u,int v,int w){
	e[++g].obj=v;
	e[g].last=head[u];
	e[g].val=w;
	head[u]=g;
}
priority_queue<pair<int,int> >q;
bool pd[2005],op;
int rev,last=0,rec,sav;
pair<int,int> check(){
	while(!q.empty()&&pd[q.top().second])q.pop();
	if(!q.empty()){
        int x=q.top().second;
        return {dist[x]-last,x};
    }
	return {511,0};
}
void update(int u){
	pd[u]=true;last=dist[u];
	for(int i=head[u];i;i=e[i].last){
		int v=e[i].obj,w=e[i].val;
		if(dist[v]>dist[u]+w){
			dist[v]=dist[u]+w;
			q.push({-dist[v],v});
		}
	}
}
void Init(int x,int len){
	for(int i=len-1;i>=0;i--)SendA(x&(1<<i));
}
void InitA(int N,int M,vector<int>U,vector<int>V,vector<int>W){
	g=0;
	for(int i=0;i<N;i++)head[i]=0,pd[i]=false;
	dist.resize(N);
	for(int i=1;i<N;i++)dist[i]=1e9;
	for(int i=0;i<M;i++)link(U[i],V[i],W[i]),link(V[i],U[i],W[i]);
	while(!q.empty())q.pop();
	q.push({0,0});
	rev=9;op=0;rec=0;update(0);
	auto [len,u]=check();Init(len,9);
}
void ReceiveA(bool x){
	rec=(rec<<1)|(int)(x);rev--;
	if(!rev){
		auto [len,u]=check();
		if(!op){
			if(len<=rec){
				op=0,rev=9;rec=0;
				update(u);
				Init(u,11);Init(check().first,9);
			}
			else sav=rec,op=1,rev=11,rec=0;
		}
		else {
			dist[rec]=sav+last;
			update(rec);
			op=0;rev=9;rec=0;
			Init(check().first,9);
		}
	}
}
vector<int> Answer(){
    return dist;
}

#include<bits/stdc++.h>
#include "Baijan.h"

using namespace std;
struct edge{
	int obj;
	int last;
	int val;
}e[1000006];
int head[2005],g;
vector<int>dist; 
void link(int u,int v,int w){
	e[++g].obj=v;
	e[g].last=head[u];
	e[g].val=w;
	head[u]=g;
}
priority_queue<pair<int,int> >q;
bool pd[2005],op;
int rev,last=0,rec,sav;
pair<int,int> check(){
	while(!q.empty()&&pd[q.top().second])q.pop();
	if(!q.empty()){
        int x=q.top().second;
        return {dist[x]-last,x};
    }
	return {511,0};
}
void update(int u){
	pd[u]=true;last=dist[u];
	for(int i=head[u];i;i=e[i].last){
		int v=e[i].obj,w=e[i].val;
		if(dist[v]>dist[u]+w){
			dist[v]=dist[u]+w;
			q.push({-dist[v],v});
		}
	}
}
void Init(int x,int len){
	for(int i=len-1;i>=0;i--)SendB(x&(1<<i));
}
void InitB(int N,int M,vector<int>U,vector<int>V,vector<int>W){
	g=0;
	for(int i=0;i<N;i++)head[i]=0,pd[i]=false;
	dist.resize(N);
	for(int i=1;i<N;i++)dist[i]=1e9;
	for(int i=0;i<M;i++)link(U[i],V[i],W[i]),link(V[i],U[i],W[i]);
	while(!q.empty())q.pop();
	q.push({0,0});
	rev=9;op=0;rec=0;update(0);
	auto [len,u]=check();Init(len,9);
}
void ReceiveB(bool x){
	rec=(rec<<1)|(int)(x);rev--;
	if(!rev){
		auto [len,u]=check();
		if(!op){
			if(len<rec){
				op=0,rev=9;rec=0;
				update(u);
				Init(u,11);Init(check().first,9);
			}
			else sav=rec,op=1,rev=11,rec=0;
		}
		else {
			dist[rec]=sav+last;
			update(rec);
			op=0;rev=9;rec=0;
			Init(check().first,9);
		}
	}
}