#include <algorithm>
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2")
#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ff first
#define ss second
#define ln "\n"
const ll INF = 2e9;
static int n;
static vector<ll> dist;
static ll sf=0, finish=0;
static vector<set<pair<ll, ll>>> gr;
static vector<pair<ll, ll>> musr;
array<ll, 3> process(){
for (ll i=0; i<n; i++){
if (dist[i]!=INF) sf=max(sf, dist[i]);
}
finish=(*max_element(dist.begin(), dist.end())!=INF);
array<ll, 3> best={INF, -1, -1};
for (ll i=0; i<n; i++){
if (dist[i]!=INF){
musr.clear();
for (auto [w, v]:gr[i]){
if (dist[v]==INF) {
best=min(best, {dist[i]+w-sf, dist[i]+w, v}); break;
} else{
musr.push_back({w, v});
}
}
for (auto x:musr) gr[i].erase(x);
}
}
return best;
}
static array<ll, 3> send = {-1, -1, -1};
static vector<ll> buffer;
void handleNewIter(){
array<ll, 3> nw = process();
if (finish) return;
// cout << "A sending weight: " << nw[0] << " + " << sf << endl;
for (ll i=0; i<9; i++){
if ((1<<i)&nw[0] or nw[0]==INF) SendA(1);
else SendA(0);
}
send=nw;
}
void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
n=N; finish=0;
buffer.clear(); gr.assign(n, set<pair<ll, ll>>());
dist.assign(n, INF); dist[0]=0; sf=0;
for (ll i=0; i<A; i++){
gr[U[i]].insert({C[i], V[i]});
gr[V[i]].insert({C[i], U[i]});
}
handleNewIter();
}
void ReceiveA(bool x) {
if (finish) return;
buffer.push_back(x);
if (buffer.size()==9){
ll w = 0;
for (ll i=0; i<9; i++){
if (buffer[i]) w+=(1<<i);
}
// cout << "A received weight: " << w << " + " << sf << endl;
if (w<send[0]){
// cout << "A Waiting for full data " << endl;
return;
}else{
if (send[0]==INF){
finish=1; return;
}
// cout << "A sending vertex: " << send[2] << endl;
for (ll i=0; i<11; i++){
if ((1<<i)&send[2]) SendA(1);
else SendA(0);
}
dist[send[2]]=send[1];
}
buffer.clear(); handleNewIter();
}else if (buffer.size()==20){
ll w = sf; for (ll i=0; i<9; i++){
if (buffer[i]) w+=(1<<i);
}
ll u=0; for (ll i=9; i<20; i++){
if (buffer[i]) u+=(1<<(i-9));
}
// cout << "A received: " << u << " & " << w << " - " << sf << endl;
dist[u]=w; buffer.clear();
handleNewIter();
}
}
vector<int> Answer() {
vector<int> ans(n);
for (ll i=0; i<n; i++) ans[i]=dist[i];
return ans;
}
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2")
#include "Baijan.h"
#include <bits/stdc++.h>
#define ll int
using namespace std;
const ll INF = 2e9;
static vector<set<pair<ll, ll>>> gr;
static int n;
static vector<ll> dist;
static ll sf = 0, finish=0;
static vector<pair<ll, ll>> musr;
static array<ll, 3> process(){
for (ll i=0; i<n; i++){
if (dist[i]!=INF) sf=max(sf, dist[i]);
}
bool unset=0;
for (ll i=0; i<n; i++){
if (dist[i]==INF) unset=1;
}
if (unset==0) {
finish=1;
}
array<ll, 3> best = {INF, -1, -1};
for (ll i=0; i<n; i++){
if (dist[i]!=INF){
musr.clear();
for (auto [w, v]:gr[i]){
if (dist[v]==INF) {best=min(best, {dist[i]+w-sf, dist[i]+w, v}); break;}
else musr.push_back({w, v});
}
for (auto x:musr) gr[i].erase(x);
}
}
return best;
}
static vector<ll> buffer;
static array<ll, 3> send = {-1, -1, -1};
static void newIter(){
buffer.clear();
send=process();
}
void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
n=N; gr.assign(n, set<pair<ll, ll>>()); finish=0;
dist.assign(n, INF); dist[0]=0; sf=0;
for (ll i=0; i<B; i++){
gr[S[i]].insert({D[i], T[i]});
gr[T[i]].insert({D[i], S[i]});
}
newIter();
}
void ReceiveB(bool y) {
if (finish) return;
buffer.push_back(y);
if (buffer.size()==9){
ll w=0;
for (ll i=0; i<9; i++){
if (buffer[i]) w+=(1<<i);
}
// cout << "B received: " << w << " aka " << w+sf << endl;
if (w<=send[0]){
for (ll i=0; i<9; i++){
if (send[0]>=INF or send[0]&(1<<i)) SendB(1);
else SendB(0);
}
// cout << "B sending (9): " << send[0] << " based on " << send[1] << " - " << sf << endl;
return;
}else{
for (ll i=0; i<9; i++){
if (send[0]&(1<<i)) SendB(1);
else SendB(0);
}
for (ll i=0; i<11; i++){
if (send[2]&(1<<i)) SendB(1);
else SendB(0);
}
// cout << "B sending (20): " << send[0] << " " << send[2] << " based on " << send[1] << " - " << sf << endl;
dist[send[2]]=send[1];
newIter();
}
}else if (buffer.size()==20){
ll w=sf;
for (ll i=0; i<9; i++){
if (buffer[i]) w+=(1<<i);
}
ll u=0;
for (ll i=9; i<20; i++){
if (buffer[i]) u+=(1<<(i-9));
}
// cout << "B received (20): " << u << " " << w << endl;
dist[u]=w; newIter();
}
}
