#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace Azer{
const int INF=INT_MAX/2;
int n;
vector<int> dpa,dpb;
vector<vector<pair<int,int>>> adj;
int dat,counter;
void send(int id,int v){
for(int i=0;i<11;i++)SendA(id>>i&1);
for(int i=0;i<20;i++)SendA(v>>i&1);
}
void dijkstra(int u){
using P = pair<int,int>;
priority_queue<P,vector<P>,greater<P>> pq;
pq.emplace(dpa[u],u);
while(!pq.empty()){
auto [d,u]=pq.top();
pq.pop();
if(d>dpa[u])continue;
for(auto [v,w]:adj[u])if(d+w<dpa[v]){
dpa[v]=d+w;
pq.emplace(d+w,v);
}
}
}
int getmin(){
int id=0;
for(int i=1;i<n;i++)if(dpa[i]<dpb[i]&&(!id||dpa[i]<dpa[id]))id=i;
if(id)dpb[id]=dpa[id];
return id;
}
void receive(int id,int v){
assert(0<=id&&id<n);
if(v<dpa[id]){
dpa[id]=v;
dijkstra(id);
}
int x=getmin();
if(id==0&&x==0)return;
send(x,dpa[x]);
}
}
void InitA(int _n, int a,vector<int> _u,vector<int> _v,vector<int> _c){
using namespace Azer;
dat=counter=0;
n=_n;
dpa.assign(n,INF);
dpb.assign(n,INF);
adj.assign(n,{});
for(int i=0;i<a;i++){
int u=_u[i],v=_v[i],c=_c[i];
adj[u].emplace_back(v,c);
adj[v].emplace_back(u,c);
}
dpa[0]=dpb[0]=0;
dijkstra(0);
int id=getmin();
send(id,dpa[id]);
}
void ReceiveA(bool x){
using namespace Azer;
dat|=int(x)<<counter;
counter++;
if(counter==31){
receive(dat&2047,dat>>11);
dat=counter=0;
}
}
vector<int> Answer(){
using namespace Azer;
return dpa;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace Baijan{
const int INF=INT_MAX/2;
int n;
vector<int> dpa,dpb;
vector<vector<pair<int,int>>> adj;
int dat,counter;
void send(int id,int v){
for(int i=0;i<11;i++)SendB(id>>i&1);
for(int i=0;i<20;i++)SendB(v>>i&1);
}
void dijkstra(int u){
using P = pair<int,int>;
priority_queue<P,vector<P>,greater<P>> pq;
pq.emplace(dpa[u],u);
while(!pq.empty()){
auto [d,u]=pq.top();
pq.pop();
if(d>dpa[u])continue;
for(auto [v,w]:adj[u])if(d+w<dpa[v]){
dpa[v]=d+w;
pq.emplace(d+w,v);
}
}
}
int getmin(){
int id=0;
for(int i=1;i<n;i++)if(dpa[i]<dpb[i]&&(!id||dpa[i]<dpa[id]))id=i;
if(id)dpb[id]=dpa[id];
return id;
}
void receive(int id,int v){
assert(0<=id&&id<n);
if(v<dpa[id]){
dpa[id]=v;
dijkstra(id);
}
int x=getmin();
if(id==0&&x==0)return;
send(x,dpa[x]);
}
}
void InitB(int _n, int b,vector<int> _u,vector<int> _v,vector<int> _c){
using namespace Baijan;
dat=counter=0;
n=_n;
dpa.assign(n,INF);
dpb.assign(n,INF);
adj.assign(n,{});
for(int i=0;i<b;i++){
int u=_u[i],v=_v[i],c=_c[i];
adj[u].emplace_back(v,c);
adj[v].emplace_back(u,c);
}
dpa[0]=dpb[0]=0;
dijkstra(0);
}
void ReceiveB(bool x){
using namespace Baijan;
dat|=int(x)<<counter;
counter++;
if(counter==31){
receive(dat&2047,dat>>11);
dat=counter=0;
}
}
