#include "Azer.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

namespace nsa{
#ifndef LCH
#define printf(...) 1
#endif
	const int WB=9;
	const int NB=11;
	const int N=2002;
	int __rbits,__cur;
	
	int n;
	vector<pair<int,int>> g[N];
	int dis[N],vis[N],ac;
	int lstdi;
	priority_queue<pair<int,int>,vector<pair<int,int>>,
		greater<pair<int,int>>>q;
	int stat=0;
	// stat=0: waiting for val
	// stat=1: waiting for id
	
	void AwaitInt(int bits){ __cur=0,__rbits=bits; }
	void SendInt(int x,int bits){
		printf("Alice send %d (%c)\n",x,"WN"[bits==NB]);
		vector<int> bs;
		for(int i=0;i<bits;i++) bs.push_back(x&1),x>>=1;
		reverse(bs.begin(),bs.end());
		for(int i:bs) SendA(i);
	}
	void ext(int u){
		for(auto [v,w]:g[u]){
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({dis[v],v});
			}
		}
	}
	void ReceiveInt(int x){
		printf("Alice receive %d\n",x);
		if(stat==0){
			if(x==505) x=2e9;
			else x+=lstdi;
			printf("%d is a value, check\n",x);
			int u;
			if(q.empty()){
				u=n;
			}else{
				u=q.top().second;
			}
			printf("cur dist is %d (%d), ",u,dis[u]);
			if(x<dis[u]){
				printf("await\n");
				lstdi=x;
				AwaitInt(NB);
				stat=1;
				return;
			}
			lstdi=dis[u];
			if(x>dis[u]){
				printf("better, send, ");
				SendInt(u,NB);
			}
			vis[u]=true;
			q.pop();
			printf("updt!\n");
			ext(u);
		}else{
			printf("%d is an id, updt dist\n",x);
			dis[x]=lstdi;
			vis[x]=true;
			ext(x);
			stat=0;
		}
		++ac;
		printf("siz q = %llu\n",q.size());
		while(!q.empty()){
			int u=q.top().second;
			if(vis[u]){
				// printf("u = %d\n",u);
				q.pop();
				continue;
			}
			printf("new top is %d (%d)\n",u,dis[u]);
			SendInt(dis[u]-lstdi,WB);
			AwaitInt(WB);
			return;
		}
		if(ac<n){
			SendInt(505,WB);
			AwaitInt(WB);
		}
	}
#ifndef LCH
#undef printf
#endif
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
		std::vector<int> C) {
	nsa::n=N;
	memset(nsa::dis,0x3f,(N+1)*sizeof(int));
	memset(nsa::vis,0,(N+1)*sizeof(int));
	nsa::ac=0;
	nsa::dis[0]=0;
	nsa::lstdi=0;
	nsa::stat=0;
	for(int i=0;i<N;i++) nsa::g[i].clear();
	for(int i=0;i<A;i++) nsa::g[U[i]].push_back({V[i],C[i]});
	for(int i=0;i<A;i++) nsa::g[V[i]].push_back({U[i],C[i]});
	nsa::q.push({0,0});
	nsa::SendInt(0,nsa::WB);
	nsa::AwaitInt(nsa::WB);
}

void ReceiveA(bool x) {
	if(!nsa::__rbits){
		fprintf(stderr,"Alice wants nothing but bob sends");
		exit(0);
	}
	nsa::__rbits--;
	nsa::__cur=(nsa::__cur<<1)+x;
	if(nsa::__rbits==0) nsa::ReceiveInt(nsa::__cur);
}

std::vector<int> Answer() {
	using namespace nsa;
	std::vector<int> ans(n);
	for(int k=0;k<n;++k) ans[k]=nsa::dis[k];
	return ans;
}

#include "Baijan.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

namespace nsb{
#ifndef LCH
#define printf(...) 1
#endif
	const int WB=9;
	const int NB=11;
	const int N=2002;
	int __rbits,__cur;
	
	int n;
	vector<pair<int,int>> g[N];
	int dis[N],vis[N];
	int lstdi,ac;
	// stat: 0=waiting for val, 1=waiting for id, 2=end
	priority_queue<pair<int,int>,vector<pair<int,int>>,
		greater<pair<int,int>>>q;
	int stat=0;
	
	void AwaitInt(int bits){ __cur=0,__rbits=bits; }
	void SendInt(int x,int bits){
		printf("Bob send %d (%c)\n",x,"WN"[bits==NB]);
		vector<int> bs;
		for(int i=0;i<bits;i++) bs.push_back(x&1),x>>=1;
		reverse(bs.begin(),bs.end());
		for(int i:bs) SendB(i);
	}
	void ext(int u){
		for(auto [v,w]:g[u]){
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({dis[v],v});
			}
		}
	}
	void ReceiveInt(int x){
		printf("Bob receive %d\n",x);
		if(stat==0){
			if(x==505) x=2e9;
			else x+=lstdi;
			printf("%d is a value, check\n",x);
			int u;
			if(q.empty()){
				u=n;
			}else{
				u=q.top().second;
			}
			printf("cur dist is %d (%d), ",u,dis[u]);
			if(x<dis[u]){
				printf("await\n");
				lstdi=x;
				AwaitInt(NB);
				stat=1;
				return;
			}
			lstdi=dis[u];
			if(x>dis[u]){
				printf("better, send, ");
				SendInt(u,NB);
			}
			vis[u]=true;
			q.pop();
			printf("updt!\n");
			ext(u);
		}else{
			printf("%d is an id, updt dist\n",x);
			dis[x]=lstdi;
			vis[x]=true;
			ext(x);
			stat=0;
		}
		++ac;
		while(!q.empty()){
			int u=q.top().second;
			if(vis[u]){
				q.pop();
				continue;
			}
			printf("new top is %d (%d)\n",u,dis[u]);
			SendInt(dis[u]-lstdi,WB);
			AwaitInt(WB);
			return;
		}
		if(ac<n){
			SendInt(505,WB);
			AwaitInt(WB);
		}
	}
#ifndef LCH
#undef printf
#endif
}

void InitB(int N, int B, std::vector<int> U, std::vector<int> V,
        std::vector<int> C) {
	nsb::n=N;
	memset(nsb::dis,0x3f,(N+1)*sizeof(int));
	memset(nsb::vis,0,(N+1)*sizeof(int));
	nsb::ac=0;
	nsb::dis[0]=0;
	nsb::lstdi=0;
	nsb::stat=0;
	for(int i=0;i<N;i++) nsb::g[i].clear();
	for(int i=0;i<B;i++) nsb::g[U[i]].push_back({V[i],C[i]});
	for(int i=0;i<B;i++) nsb::g[V[i]].push_back({U[i],C[i]});
	nsb::q.push({0,0});
	nsb::SendInt(0,nsb::WB);
	nsb::AwaitInt(nsb::WB);
}

void ReceiveB(bool y) {
	if(!nsb::__rbits){
		fprintf(stderr,"Bob wants nothing but alice sends");
		exit(0);
	}
	nsb::__rbits--;
	nsb::__cur=(nsb::__cur<<1)+y;
	if(nsb::__rbits==0) nsb::ReceiveInt(nsb::__cur);
}