#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
namespace{
int counter=0, val=0, phase=0, tempval, mn;
vector<int> dist, done, notdone;
vector<bool> del;
vector<deque<pii> > graph;
}
void InitA(int n, int a, vector<int> u, vector<int> v, vector<int> c){
done.clear();
dist.clear();
graph.clear();
del.clear();
del.resize(n, 0);
done.resize(1, 0);
dist.resize(n, INT_MAX/2);
graph.resize(n);
dist[0]=counter=val=phase=0;
del[0]=1;
for (int i=1; i<n; ++i)notdone.pb(i);
for (int i=0; i<a; ++i){
graph[u[i]].pb(mp(c[i], v[i]));
graph[v[i]].pb(mp(c[i], u[i]));
}
for (int i=0; i<n; ++i)sort(graph[i].begin(), graph[i].end());
}
void ReceiveA(bool x){
++counter;
val=val*2+x;
if (!phase&&counter==9){
int dj=INT_MAX/2, best;
mn=INT_MAX/2;
for (auto node:done){
while (graph[node].size()&&del[graph[node][0].se])graph[node].pop_front();
if (graph[node].empty())continue;
mn=min(mn, dist[node]);
if (dist[node]+graph[node][0].fi<dj)dj=dist[node]+graph[node][0].fi, best=graph[node][0].se;
}
if (dj-mn<val){
SendA(0);
dist[best]=dj;
done.pb(best);
del[best]=1;
int id=0;
for (int i=0; i<notdone.size(); ++i)if (notdone[i]==best)id=i;
notdone.erase(find(notdone.begin(), notdone.end(), best));
for (int i=log2(notdone.size()+1)+1; i>=0; --i)SendA((1<<i)&id);
for (int i=8; i>=0; --i)SendA((1<<i)&(dj-mn));
}
else{
SendA(1);
phase=1;
}
counter=val=0;
}
if (phase==1&&counter==log2(notdone.size())+1){
tempval=val;
phase=2;
counter=val=0;
}
if (phase==2&&counter==9){
int best=notdone[tempval];
dist[best]=val+mn;
done.pb(best);
del[best]=1;
notdone.erase(find(notdone.begin(), notdone.end(), best));
phase=counter=val=0;
}
}
vector<int> Answer(){
return dist;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
namespace{
int counter=0, val=0, phase=0, tempval, mn=INT_MAX/2, dj=INT_MAX/2, best;
vector<int> dist, done, notdone;
vector<bool> del;
vector<deque<pii> > graph;
void sendover(){
mn=dj=INT_MAX/2;
for (auto node:done){
while (graph[node].size()&&del[graph[node][0].se])graph[node].pop_front();
if (graph[node].empty())continue;
mn=min(mn, dist[node]);
if (dist[node]+graph[node][0].fi<dj)dj=dist[node]+graph[node][0].fi, best=graph[node][0].se;
}
for (int i=8; i>=0; --i)SendB((1<<i)&(dj-mn));
}
}
void InitA(int n, int a, vector<int> u, vector<int> v, vector<int> c){
done.clear();
dist.clear();
graph.clear();
del.clear();
del.resize(n, 0);
done.resize(1, 0);
dist.resize(n, INT_MAX/2);
graph.resize(n);
dist[0]=counter=val=phase=0;
del[0]=1;
for (int i=1; i<n; ++i)notdone.pb(i);
for (int i=0; i<a; ++i){
graph[u[i]].pb(mp(c[i], v[i]));
graph[v[i]].pb(mp(c[i], u[i]));
}
for (int i=0; i<n; ++i)sort(graph[i].begin(), graph[i].end());
sendover();
}
void ReceiveB(bool x){
++counter;
val=val*2+x;
if (!phase){
if (val){
dist[best]=dj;
done.pb(best);
del[best]=1;
int id=0;
for (int i=0; i<notdone.size(); ++i)if (notdone[i]==best)id=i;
notdone.erase(find(notdone.begin(), notdone.end(), best));
for (int i=log2(notdone.size()+1)+1; i>=0; --i)SendB((1<<i)&id);
for (int i=8; i>=0; --i)SendB((1<<i)&(dj-mn));
sendover();
}
else phase=1;
val=counter=0;
}
if (phase==1&&counter==log2(notdone.size())+1){
tempval=val;
phase=2;
counter=val=0;
}
if (phase==2&&counter==9){
int best=notdone[tempval];
dist[best]=val+mn;
done.pb(best);
del[best]=1;
notdone.erase(find(notdone.begin(), notdone.end(), best));
phase=counter=val=0;
}
}
