#include<bits/stdc++.h>
#include "Azer.h"
#define inf 1e9
using namespace std;
namespace {
int n,cnt1,cnt2,nr,dist1,dist2;
bool ok;
vector<pair<int,int>>*g;
vector<int>dist;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
void update(int nod)
{
for(auto it:g[nod]){
if (dist[nod]+it.second<-dist[it.first]){
dist[it.first]=-(dist[nod]+it.second);
pq.push(make_pair(dist[nod]+it.second,it.first));
}
}
}
void query()
{
int i;
if (cnt1==0)
return ;
cnt1--;
while(1){
if (pq.empty()){
dist2=511;
for(i=8;i>=0;i--)
SendA((dist2>>i)&1);
return ;
}
pair<int,int>aux=pq.top();
if (aux.first+dist[aux.second]==0){
dist2=aux.first-dist1;
for(i=8;i>=0;i--)
SendA((dist2>>i)&1);
return ;
}
pq.pop();
}
}
}
void InitA(int N,int a,vector<int>u,vector<int>v,vector<int>c)
{
n=N;
g=new vector<pair<int,int>>[n];
int i;
for(i=0;i<a;i++){
g[u[i]].push_back(make_pair(v[i],c[i]));
g[v[i]].push_back(make_pair(u[i],c[i]));
}
dist.push_back(0);
for(i=1;i<n;i++)
dist.push_back(-inf);
cnt1=n-1;
dist1=0;
update(0);
query();
ok=0;
cnt2=0;
nr=0;
}
void ReceiveA(bool x)
{
int i;
nr*=2;
nr+=x;
if (ok){
cnt2++;
if (cnt2==11){
dist1+=dist2;
dist[nr]=dist1;
update(nr);
query();
ok=0;
cnt2=0;
nr=0;
}
}
else{
cnt2++;
if (cnt2==9){
if (nr>=dist2){
int aux=pq.top().second;
for(i=10;i>=0;i--)
SendA((aux>>i)&1);
dist1+=dist2;
dist[aux]=dist1;
update(aux);
query();
}
else{
dist2=nr;
ok=1;
}
cnt2=0;
nr=0;
}
}
}
std::vector<int> Answer()
{
return dist;
}
#include<bits/stdc++.h>
#define inf 1e9
#include "Baijan.h"
using namespace std;
namespace {
int n,cnt1,cnt2,nr,dist1,dist2;
bool ok;
vector<pair<int,int>>*g;
vector<int>dist;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
void update(int nod)
{
for(auto it:g[nod]){
if (dist[nod]+it.second<-dist[it.first]){
dist[it.first]=-(dist[nod]+it.second);
pq.push(make_pair(dist[nod]+it.second,it.first));
}
}
}
void query()
{
int i;
if (cnt1==0)
return ;
cnt1--;
while(1){
if (pq.empty()){
dist2=511;
for(i=8;i>=0;i--)
SendB((dist2>>i)&1);
return ;
}
pair<int,int>aux=pq.top();
if (aux.first+dist[aux.second]==0){
dist2=aux.first-dist1;
for(i=8;i>=0;i--)
SendB((dist2>>i)&1);
return ;
}
pq.pop();
}
}
}
void InitB(int N,int b,vector<int>s,vector<int>t,vector<int>d)
{
n=N;
int i;
g=new vector<pair<int, int>>[n];
for(i=0;i<b;i++){
g[s[i]].push_back(make_pair(t[i],d[i]));
g[t[i]].push_back(make_pair(s[i],d[i]));
}
dist.push_back(0);
for(i=1;i<N;i++)
dist.push_back(-inf);
cnt1=n-1;
dist1=0;
update(0);
query();
ok=0;
cnt2=0;
nr=0;
}
void ReceiveB(bool y)
{
int i;
nr*=2;
nr+=y;
if (ok){
++cnt2;
if (cnt2==11){
dist1+=dist2;
dist[nr]=dist1;
update(nr);
query();
ok=0;
cnt2=0;
nr=0;
}
}
else{
++cnt2;
if (cnt2==9){
if (nr>dist2){
int aux=pq.top().second;
for(i=10;i>=0;i--)
SendB((aux>>i)&1);
dist1+=dist2;
dist[aux]=dist1;
update(aux);
query();
}
else{
dist2=nr;
ok=1;
}
cnt2=0;
nr=0;
}
}
}
