#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int maxn = 2000;
const int inf = 1123123123;
bool fg;
int n, m;
int d[maxn], u[maxn], v[maxn], c[maxn];
vector < bool > rec;
pair < int, int > get(){
int to = -1, cst = inf;
for(int i = 0; i < m; i++)
if(d[u[i]] < inf && d[v[i]] == inf && d[u[i]] + c[i] < cst)
cst = d[u[i]] + c[i], to = v[i];
for(int i = 0; i < m; i++)
if(d[u[i]] == inf && d[v[i]] < inf && d[v[i]] + c[i] < cst)
cst = d[v[i]] + c[i], to = u[i];
return {to, cst};
}
}
void InitA(int N, int M, vector< int > U, vector< int > V, vector < int > C){
n = N, m = M;
for(int i = 0; i < n; i++) d[i] = inf;
for(int i = 0; i < m; i++) u[i] = U[i], v[i] = V[i], c[i] = C[i];
d[0] = 0;
auto [to, cst] = get();
for(int bit = 10; bit >= 0; bit--) SendA((to >> bit & 1));
for(int bit = 19; bit >= 0; bit--) SendA((cst >> bit & 1));
}
void ReceiveA(bool x){
if(!fg){
if(x){
auto [to, cst] = get();
if(cst == inf) return;
d[to] = cst, rec.clear();
to = get().first, cst = get().second;
for(int bit = 10; bit >= 0; bit--) SendA((to >> bit & 1));
for(int bit = 19; bit >= 0; bit--) SendA((cst >> bit & 1));
}
else{
fg = 1;
}
return;
}
else{
rec.push_back(x);
if(rec.size() < 31) return;
int to = 0, cst = 0, j = 0;
for(int bit = 10; bit >= 0; bit--) to |= (rec[j++] << bit);
for(int bit = 19; bit >= 0; bit--) cst |= (rec[j++] << bit);
if(cst == (1 << 20) - 1) return;
d[to] = cst, rec.clear(), fg = 0;
to = get().first, cst = get().second;
for(int bit = 10; bit >= 0; bit--) SendA((to >> bit & 1));
for(int bit = 19; bit >= 0; bit--) SendA((cst >> bit & 1));
}
}
vector < int > Answer(){
vector < int > ans(n);
for(int i = 0; i < n; i++) ans[i] = d[i];
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int maxn = 2000;
const int inf = 1123123123;
int n, m;
int d[maxn], u[maxn], v[maxn], c[maxn];
vector < bool > rec;
pair < int, int > get(){
int to = -1, cst = inf;
for(int i = 0; i < m; i++)
if(d[u[i]] < inf && d[v[i]] == inf && d[u[i]] + c[i] < cst)
cst = d[u[i]] + c[i], to = v[i];
for(int i = 0; i < m; i++)
if(d[u[i]] == inf && d[v[i]] < inf && d[v[i]] + c[i] < cst)
cst = d[v[i]] + c[i], to = u[i];
return {to, cst};
}
}
void InitB(int N, int M, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
n = N, m = M;
for(int i = 0; i < n; i++) d[i] = inf;
for(int i = 0; i < m; i++) u[i] = S[i], v[i] = T[i], c[i] = D[i];
d[0] = 0;
}
void ReceiveB(bool y){
rec.push_back(y);
if(rec.size() < 31) return;
int to = 0, cst = 0, j = 0;
for(int bit = 10; bit >= 0; bit--) to |= (rec[j++] << bit);
for(int bit = 19; bit >= 0; bit--) cst |= (rec[j++] << bit);
rec.clear();
auto [to2, cst2] = get();
if(cst <= cst2){
d[to] = cst;
SendB(1);
return;
}
d[to2] = cst2;
SendB(0);
for(int bit = 10; bit >= 0; bit--) SendB((to2 >> bit & 1));
for(int bit = 19; bit >= 0; bit--) SendB((cst2 >> bit & 1));
}
