#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#include "Azer.h"
namespace
{
int n;
vector<pair<int,int>>komsu[2023];
int vis[2023],dp[2023];
int getworst(){
int x=0;
for(int i=0;i<n;i++){
if(vis[i])x=max(x,dp[i]);
}
return x;
}
int getnext(){
int x=-1;
for(int i=0;i<n;i++){
if(vis[i])continue;
if(x==-1||dp[i]<dp[x]){
x=i;
}
}
return x;
}
void send(int x,int bit){
for(int i=0;i<bit;i++){
SendA((x>>i)&1);
}
}
int costb=0,tar=0;
int mod=0;
}
void InitA(int N,int A,vector<int>U,vector<int>V,vector<int>C){
n=N;
for(int i=0;i<n;i++){
dp[i]=1e9;
vis[i]=0;
komsu[i].clear();
}
mod=costb=tar=0;
for(int i=0;i<A;i++){
komsu[U[i]].pb({V[i],C[i]});
komsu[V[i]].pb({U[i],C[i]});
}
vis[0]=1;
dp[0]=0;
for(auto x:komsu[0]){
dp[x.fr]=min(dp[x.fr],x.sc);
}
send(min(511,dp[getnext()]-getworst()),9);
}
void ReceiveA(bool X){
int bit=X;
if(mod<9)costb+=(bit<<mod);
else tar+=(bit<<(mod-9));
mod++;
if(mod==9){
if(min(511,dp[getnext()]-getworst())<=costb){
tar=getnext();
send(tar,11);
vis[tar]=1;
for(auto x:komsu[tar]){
dp[x.fr]=min(dp[x.fr],dp[tar]+x.sc);
}
mod=0;
costb=0;
tar=0;
int x=getnext();
if(x!=-1)send(min(511,dp[x]-getworst()),9);
}
}
else if(mod==20){
dp[tar]=getworst()+costb;
vis[tar]=1;
for(auto x:komsu[tar]){
dp[x.fr]=min(dp[x.fr],dp[tar]+x.sc);
}
mod=0;
costb=0;
tar=0;
int x=getnext();
if(x!=-1)send(min(511,dp[x]-getworst()),9);
}
}
vector<int> Answer(){
vector<int>ans(n);
for(int i=0;i<n;i++){
ans[i]=dp[i];
}
return ans;
}
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#include "Baijan.h"
namespace
{
int nB;
vector<pair<int,int>>komsuB[2023];
int visB[2023],dpB[2023];
int getworstB(){
int x=0;
for(int i=0;i<nB;i++){
if(visB[i])x=max(x,dpB[i]);
}
return x;
}
int getnextB(){
int x=-1;
for(int i=0;i<nB;i++){
if(visB[i])continue;
if(x==-1||dpB[i]<dpB[x]){
x=i;
}
}
return x;
}
void sendB(int x,int bit){
for(int i=0;i<bit;i++){
SendB((x>>i)&1);
}
}
int costa=0,tarB=0;
int modB=0;
}
void InitB(int N,int B,vector<int>S,vector<int>T,vector<int>D){
nB=N;
for(int i=0;i<nB;i++){
dpB[i]=1e9;
visB[i]=0;
komsuB[i].clear();
}
modB=costa=tarB=0;
for(int i=0;i<B;i++){
komsuB[S[i]].pb({T[i],D[i]});
komsuB[T[i]].pb({S[i],D[i]});
}
visB[0]=1;
dpB[0]=0;
for(auto x:komsuB[0]){
dpB[x.fr]=min(dpB[x.fr],x.sc);
}
}
void ReceiveB(bool Y){
int bit=Y;
if(modB<9)costa+=(bit<<modB);
else tarB+=(bit<<(modB-9));
modB++;
if(modB==9){
sendB(min(511,dpB[getnextB()]-getworstB()),9);
if(costa>min(511,dpB[getnextB()]-getworstB())){
tarB=getnextB();
sendB(tarB,11);
visB[tarB]=1;
for(auto x:komsuB[tarB]){
dpB[x.fr]=min(dpB[x.fr],dpB[tarB]+x.sc);
}
modB=0;
costa=0;
tarB=0;
}
}
else if(modB==20){
dpB[tarB]=costa;
visB[tarB]=1;
for(auto x:komsuB[tarB]){
dpB[x.fr]=min(dpB[x.fr],dpB[tarB]+x.sc);
}
modB=0;
tarB=0;
costa=0;
}
}
