#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
struct dijik{
vector<int> d;
vector<vector<pair<int,int>>> graph;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
void add(int u,int dist){
d[u]=dist;
for(pair<int,int> &x:graph[u]){
int v=x.first,w=x.second;
pq.push({d[u]+w,v});
}
while(!pq.empty()&&d[pq.top().second]!=-1){
pq.pop();
}
}
void init(int n,int m,vector<int> &u,vector<int> &v,vector<int> &c){
d.assign(n,-1);
graph.resize(n);
for(int i=0;i<n;i++){
int bruh=1e6;
pq.push({bruh+1,i});
}
for(int i=0;i<m;i++){
graph[u[i]].push_back({v[i],c[i]});
graph[v[i]].push_back({u[i],c[i]});
}
add(0,0);
}
};
const int valBit=20,idxBit=11;
dijik bus;
string toBin(int x,int limit){
string s="";
for(int i=limit-1;i>=0;i--){
if(x&(1<<i)){
s+='1';
}
else{
s+='0';
}
}
return s;
}
int toInt(string s){
int ans=0;
for(int i=0;i<s.length();i++){
ans=(ans*2+(s[i]-'0'));
}
return ans;
}
void InitA(int n,int m,vector<int> u,vector<int> v,vector<int> c){
bus.init(n,m,u,v,c);
if(bus.pq.empty()){
return;
}
string send=toBin(bus.pq.top().first,valBit);
SendA(false);
for(int i=0;i<send.length();i++){
if(send[i]=='1'){
SendA(true);
}
else{
SendA(false);
}
}
}
void processA(string s){
if(s=="1"){
int u=bus.pq.top().second,dist=bus.pq.top().first;
bus.add(u,dist);
if(bus.pq.empty()){
return;
}
int nxt=bus.pq.top().first;
string send=toBin(dist,valBit)+toBin(u,idxBit)+toBin(nxt,valBit);
SendA(true);
for(int i=0;i<send.length();i++){
if(send[i]=='1'){
SendA(true);
}
else{
SendA(false);
}
}
return;
}
int dist=toInt(s.substr(0,valBit)),u=toInt(s.substr(valBit,idxBit));
bus.add(u,dist);
if(bus.pq.empty()){
return;
}
string send=toBin(bus.pq.top().first,valBit);
SendA(false);
for(int i=0;i<send.length();i++){
if(send[i]=='1'){
SendA(true);
}
else{
SendA(false);
}
}
}
int modeA=-1;
string currA="";
void ReceiveA(bool x){
if(modeA==-1){
if(x){
processA("1");
}
else{
modeA=0;
}
return;
}
if(x){
currA+='1';
}
else{
currA+='0';
}
if(currA.length()==valBit+idxBit){
processA(currA);
currA="",modeA=-1;
}
}
vector<int> Answer(){
return bus.d;
}
#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
struct dijik2{
vector<int> d;
vector<vector<pair<int,int>>> graph;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
void add(int u,int dist){
d[u]=dist;
for(pair<int,int> &x:graph[u]){
int v=x.first,w=x.second;
pq.push({d[u]+w,v});
}
while(!pq.empty()&&d[pq.top().second]!=-1){
pq.pop();
}
}
void init(int n,int m,vector<int> &u,vector<int> &v,vector<int> &c){
d.assign(n,-1);
graph.resize(n);
for(int i=0;i<n;i++){
int bruh=1e6;
pq.push({bruh+1,i});
}
for(int i=0;i<m;i++){
graph[u[i]].push_back({v[i],c[i]});
graph[v[i]].push_back({u[i],c[i]});
}
add(0,0);
}
};
const int valBit2=20,idxBit2=11;
dijik2 rail;
string toBin2(int x,int limit){
string s="";
for(int i=limit-1;i>=0;i--){
if(x&(1<<i)){
s+='1';
}
else{
s+='0';
}
}
return s;
}
int toInt2(string s){
int ans=0;
for(int i=0;i<s.length();i++){
ans=(ans*2+(s[i]-'0'));
}
return ans;
}
void InitB(int n,int m,vector<int> s,vector<int> t,vector<int> d){
rail.init(n,m,s,t,d);
}
void processB(string s){
if(s.length()==valBit2+idxBit2){
int dist=toInt2(s.substr(0,valBit2)),u=toInt2(s.substr(valBit2,idxBit2));
rail.add(u,dist);
return;
}
int val=toInt2(s),dist=rail.pq.top().first;
if(val<dist){
SendB(true);
}
else{
int u=rail.pq.top().second;
rail.add(u,dist);
string send=toBin2(dist,valBit2)+toBin2(u,idxBit2);
SendB(false);
for(int i=0;i<send.length();i++){
if(send[i]=='1'){
SendB(true);
}
else{
SendB(false);
}
}
}
}
int modeB=-1;
string currB="";
void ReceiveB(bool y){
if(modeB==-1){
if(y){
modeB=1;
}
else{
modeB=0;
}
return;
}
if(y){
currB+='1';
}
else{
currB+='0';
}
if(!modeB){
if(currB.length()==valBit2){
processB(currB);
currB="",modeB=-1;
}
}
else{
if(currB.length()==valBit2+idxBit2){
processB(currB);
}
else if(currB.length()==2*valBit2+idxBit2){
processB(currB.substr(valBit2+idxBit2,valBit2));
currB="",modeB=-1;
}
}
}
