#include "Azer.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define all(a) begin(a),end(a)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';
namespace {
priority_queue<pii> pq;
const int N=300010;
int n,la,cn,curn,bn,res[N],ther;
vector<pii> ch[N];
bool bio[N];
bool expect11;
void send9(int num)
{
num=min(num,511);
vi v;
for (int i=0;i<9;++i)
{
v.pb(num%2);
num/=2;
}
reverse(all(v));
for (auto a: v) SendA(a);
}
void send11(int num)
{
num=min(num,2047);
vi v;
for (int i=0;i<11;++i)
{
v.pb(num%2);
num/=2;
}
reverse(all(v));
for (auto a: v) SendA(a);
}
void work(int num)
{
while (bio[pq.top().y]) pq.pop();
//cout<<"A "<<pq.top().x<<' '<<pq.top().y<<' '<<la<<endl;
if (expect11)
{
la+=ther;
res[num]=la;
bio[num]=1;
++bn;
if (bn==n) return;
for (auto a: ch[num]) pq.push({-res[num]-a.y,a.x});
while (bio[pq.top().y]) pq.pop();
expect11=0;
send9(-pq.top().x-la);
}
else
{
int njre=num+la;
int more=-pq.top().x;
if (more<njre)
{
bio[pq.top().y]=1;
res[pq.top().y]=more;
++bn;
for (auto a: ch[pq.top().y]) pq.push({-res[pq.top().y]-a.y,a.x});
la=more;
send11(pq.top().y);
if (bn==n) return;
while (bio[pq.top().y]) pq.pop();
send9(-pq.top().x-la);
}
else expect11=1,ther=num;
}
}
}
void InitA(int N, int A, vi U, vi V, vi C)
{
n=N;
for (int i=0;i<A;++i)
{
ch[U[i]].eb(V[i],C[i]);
ch[V[i]].eb(U[i],C[i]);
}
for (int i=0;i<N;++i) pq.push({-MOD,2047});
bio[0]=1;
for (auto a: ch[0]) pq.push({-a.y,a.x});
++bn;
if (bn==n) return;
send9(-pq.top().x-la);
}
void ReceiveA(bool x) {
++cn;
curn=curn*2+x;
if ((cn==9 && !expect11) || (cn==11 && expect11))
{
//cout<<"A got number "<<curn<<endl;
work(curn);
curn=0;
cn=0;
}
}
vi Answer() {
vi ans(n);
for (int k = 0; k < n; ++k) {
ans[k] = res[k];
}
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(a) begin(a),end(a)
using namespace std;
namespace {
priority_queue<pii> pq;
const int N=300010;
int n,la,cn,curn,res[N],ther;
vector<pii> ch[N];
bool bio[N];
bool expect11;
void send9(int num)
{
num=min(num,511);
vi v;
for (int i=0;i<9;++i)
{
v.pb(num%2);
num/=2;
}
reverse(all(v));
for (auto a: v) SendB(a);
}
void send11(int num)
{
num=min(num,2047);
vi v;
for (int i=0;i<11;++i)
{
v.pb(num%2);
num/=2;
}
reverse(all(v));
for (auto a: v) SendB(a);
}
void work(int num)
{
while (bio[pq.top().y]) pq.pop();
//cout<<"B "<<pq.top().x<<' '<<pq.top().y<<' '<<la<<endl;
if (expect11)
{
la+=ther;
res[num]=la;
bio[num]=1;
for (auto a: ch[num]) pq.push({-res[num]-a.y,a.x});
while (bio[pq.top().y]) pq.pop();
expect11=0;
//send9(-pq.top().x-la);
}
else
{
int njre=num+la;
int more=-pq.top().x;
if (more<=njre)
{
bio[pq.top().y]=1;
res[pq.top().y]=more;
for (auto a: ch[pq.top().y]) pq.push({-res[pq.top().y]-a.y,a.x});
send9(more-la);
la=more;
send11(pq.top().y);
while (bio[pq.top().y]) pq.pop();
}
else
{
expect11=1;
ther=num;
send9(more-la);
}
}
}
} // namespace
void InitB(int N, int A, vi U, vi V, vi C)
{
n=N;
for (int i=0;i<A;++i)
{
ch[U[i]].eb(V[i],C[i]);
ch[V[i]].eb(U[i],C[i]);
}
for (int i=0;i<N;++i) pq.push({-1e9,2047});
bio[0]=1;
for (auto a: ch[0]) pq.push({-a.y,a.x});
}
void ReceiveB(bool y) {
++cn;
curn=curn*2+y;
if ((cn==9 && !expect11) || (cn==11 && expect11))
{
//cout<<"B got number "<<curn<<endl;
work(curn);
curn=0;
cn=0;
}
}
