#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int maxn = 900;
const int maxm = 500000;
const int inf = 1123123123;
bool fg;
int n, m;
int d[maxn], u[maxm], v[maxm], c[maxm];
set < pair < int, int > > reb;
vector < bool > rec;
vector < int > g[maxn];
pair < int, int > get(){
while(!reb.empty()){
int id = (reb.begin() -> second);
if(d[u[id]] < inf && d[v[id]] < inf) reb.erase(reb.begin());
else break;
}
if(reb.empty()) return {0, inf};
int id = (reb.begin() -> second);
int to = (d[u[id]] == inf ? u[id] : v[id]);
int cst = c[id];
if(d[u[id]] < inf) cst += d[u[id]];
else cst += d[v[id]];
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];
for(int i = 0; i < m; i++) g[u[i]].push_back(i), g[v[i]].push_back(i);
d[0] = 0;
for(int i : g[0]) reb.insert({c[i], i});
auto [to, cst] = get();
for(int bit = 9; 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;
if(d[to] == inf && cst < inf){
d[to] = cst;
for(int i : g[to]){
if(u[i] == to && d[v[i]] == inf) reb.insert({d[to] + c[i], i});
if(v[i] == to && d[u[i]] == inf) reb.insert({d[to] + c[i], i});
}
}
rec.clear();
to = get().first, cst = get().second;
for(int bit = 9; 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() < 30) return;
int to = 0, cst = 0, j = 0;
for(int bit = 9; bit >= 0; bit--) to |= (rec[j++] << bit);
for(int bit = 19; bit >= 0; bit--) cst |= (rec[j++] << bit);
if(cst == (1 << 20) - 1) return;
if(d[to] == inf && cst < inf){
d[to] = cst;
for(int i : g[to]){
if(u[i] == to && d[v[i]] == inf) reb.insert({d[to] + c[i], i});
if(v[i] == to && d[u[i]] == inf) reb.insert({d[to] + c[i], i});
}
}
rec.clear(), fg = 0;
to = get().first, cst = get().second;
for(int bit = 9; 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 = 900;
const int maxm = 5000000;
const int inf = 1123123123;
int n, m;
int d[maxn], u[maxm], v[maxm], c[maxm];
set < pair < int, int > > reb;
vector < bool > rec;
vector < int > g[maxn];
pair < int, int > get(){
while(!reb.empty()){
int id = (reb.begin() -> second);
if(d[u[id]] < inf && d[v[id]] < inf) reb.erase(reb.begin());
else break;
}
if(reb.empty()) return {0, inf};
int id = (reb.begin() -> second);
int to = (d[u[id]] == inf ? u[id] : v[id]);
int cst = c[id];
if(d[u[id]] < inf) cst += d[u[id]];
else cst += d[v[id]];
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];
for(int i = 0; i < m; i++) g[u[i]].push_back(i), g[v[i]].push_back(i);
d[0] = 0;
for(int i : g[0]) reb.insert({c[i], i});
}
void ReceiveB(bool y){
rec.push_back(y);
if(rec.size() < 30) return;
int to = 0, cst = 0, j = 0;
for(int bit = 9; 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){
if(d[to] == inf && cst < inf){
d[to] = cst;
for(int i : g[to]){
if(u[i] == to && d[v[i]] == inf) reb.insert({d[to] + c[i], i});
if(v[i] == to && d[u[i]] == inf) reb.insert({d[to] + c[i], i});
}
}
SendB(1);
return;
}
if(d[to2] == inf && cst2 < inf){
d[to2] = cst2;
for(int i : g[to2]){
if(u[i] == to2 && d[v[i]] == inf) reb.insert({d[to2] + c[i], i});
if(v[i] == to2 && d[u[i]] == inf) reb.insert({d[to2] + c[i], i});
}
}
SendB(0);
for(int bit = 9; bit >= 0; bit--) SendB((to2 >> bit & 1));
for(int bit = 19; bit >= 0; bit--) SendB((cst2 >> bit & 1));
}
