#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;
int cnt=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=cnt=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);
}
int t=getnext();
if(t!=-1)t=dp[t];
else t=1e9;
if(cnt<n-1)send(min(511,t-getworst()),9);
}
void ReceiveA(bool X){
int bit=X;
if(mod<9)costb+=(bit<<mod);
else tar+=(bit<<(mod-9));
mod++;
if(mod==9){
int t=getnext();
if(t!=-1)t=dp[t];
else t=1e9;
if(min(511,t-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();
cnt++;
if(x!=-1)x=dp[x];
else x=1e9;
if(cnt<n-1)send(min(511,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)x=dp[x];
else x=1e9;
cnt++;
if(cnt<n-1)send(min(511,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 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++){
SendB((x>>i)&1);
}
}
int costa=0,tar=0;
int mod=0;
}
void InitB(int N,int B,vector<int>S,vector<int>T,vector<int>D){
n=N;
for(int i=0;i<n;i++){
dp[i]=1e9;
vis[i]=0;
komsu[i].clear();
}
mod=costa=tar=0;
for(int i=0;i<B;i++){
komsu[S[i]].pb({T[i],D[i]});
komsu[T[i]].pb({S[i],D[i]});
}
vis[0]=1;
dp[0]=0;
for(auto x:komsu[0]){
dp[x.fr]=min(dp[x.fr],x.sc);
}
}
void ReceiveB(bool Y){
int bit=Y;
if(mod<9)costa+=(bit<<mod);
else tar+=(bit<<(mod-9));
mod++;
if(mod==9){
int t=getnext();
if(t!=-1)t=dp[t];
else t=1e9;
send(min(511,t-getworst()),9);
if(costa>min(511,t-getworst())){
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;
costa=0;
tar=0;
}
}
else if(mod==20){
dp[tar]=getworst()+costa;
vis[tar]=1;
for(auto x:komsu[tar]){
dp[x.fr]=min(dp[x.fr],dp[tar]+x.sc);
}
mod=0;
tar=0;
costa=0;
}
}
