#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;
int last=0;
void add(int u,int dist){
d[u]=dist;
assert(dist>=last);
last=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=9,idxBit=11;
dijik bus;
string toBin(int x,int limit){
x=min(x,(1<<limit)-1);
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-bus.last,valBit);
for(int i=0;i<send.length();i++){
if(send[i]=='1'){
SendA(true);
}
else{
SendA(false);
}
}
}
void processA(string s){
//cout << "PROCESSA " << s << endl;
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(u,idxBit)+toBin(nxt-bus.last,valBit);
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))+bus.last,u=toInt(s.substr(valBit,idxBit));
bus.add(u,dist);
if(bus.pq.empty()){
return;
}
string send=toBin(bus.pq.top().first-bus.last,valBit);
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;
int last=0;
void add(int u,int dist){
d[u]=dist;
assert(dist>=last);
last=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);
}
};
struct commu2{
const int valBit=9,idxBit=11;
string toBin(int x,int limit){
x=min(x,(1<<limit)-1);
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;
}
};
dijik2 rail;
commu2 cB;
void InitB(int n,int m,vector<int> s,vector<int> t,vector<int> d){
rail.init(n,m,s,t,d);
}
int modeB=0;
int info;
void processB(string s){
//cout << "PROCESSB " << s << endl;
if(s.length()==cB.idxBit){
modeB=0;
int dist=info+rail.last,u=cB.toInt(s);
rail.add(u,dist);
return;
}
int val=cB.toInt(s)+rail.last,dist=rail.pq.top().first;
info=val;
if(val<dist){
modeB=1;
SendB(true);
}
else{
modeB=0;
int u=rail.pq.top().second;
string send=cB.toBin(dist-rail.last,cB.valBit)+cB.toBin(u,cB.idxBit);
rail.add(u,dist);
SendB(false);
for(int i=0;i<send.length();i++){
if(send[i]=='1'){
SendB(true);
}
else{
SendB(false);
}
}
}
}
string currB="";
void ReceiveB(bool y){
if(y){
currB+='1';
}
else{
currB+='0';
}
if(!modeB){
if(currB.length()==cB.valBit){
processB(currB);
currB="";
}
}
else{
if(currB.length()==cB.idxBit){
processB(currB);
currB="";
}
}
}
