#include "Azer.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define llinf 1000000000 // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
using ld = long double;
using ll = int;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld,ld>;
static const ll maxn = 2005;
static const ll lgn = 11;
static const ll lgd = 9;
static ll n;
static vector<pll> g[maxn];
static ll dis[maxn];
static bool upd[maxn];
static void dajk(ll u){
if(u==0) return;
priority_queue<pll> pq;
pq.push({-dis[u],u});
while(si(pq)){
ll d = -pq.top().fi,u = pq.top().sc; pq.pop();
if(dis[u]!=d) continue;
for(pll p : g[u]){
ll s = p.fi,w = p.sc;
if(dis[s]>dis[u]+w){
dis[s] = dis[u] + w;
pq.push({-dis[s],s});
upd[s] = 1;
}
}
}
}
static ll cmx = 0;
static void senduj(ll u){
if(u==0){
for(ll i = 0;i<lgn+lgd;i++) SendA(0);
return;
}
// cerr<<"SA: ";
// dbg(u);
for(ll j = 0;j<lgn;j++){
if((1<<j)&u) SendA(1);
else SendA(0);
}
ll disu = dis[u]-cmx;
for(ll j = 0;j<lgd;j++){
if((1<<j)&disu) SendA(1);
else SendA(0);
}
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
n = N;
for(ll i = 0;i<A;i++){
ll x = U[i],y = V[i],w = C[i];
x++; y++;
g[x].pb({y,w});
g[y].pb({x,w});
}
for(ll i = 1;i<=n;i++) dis[i] = llinf;
dis[1] = 0;
dajk(1);
// ceri(dis,1,n);
senduj(1);
}
static ll cnt = 0;
static vector<bool> cur;
static pll conv(){
ll u = 0,disu = 0;
for(ll j = 0;j<lgn;j++){
u+=(1<<j)*cur[j];
}
for(ll j = lgn;j<lgn+lgd;j++){
disu+=(1<<(j-lgn))*cur[j];
}
return {u,disu};
}
void ReceiveA(bool x) {
cur.pb(x); cnt++;
if(cnt!=lgn+lgd) return;
pll p = conv();
cur.clear();
cnt = 0;
ll u = p.fi;
// cerr<<"A: "<<u<< " "<<cmx<<" "<<p.sc<<endl;
if(u){
dis[u] = min(dis[u],cmx+p.sc);
cmx = max(cmx,dis[u]);
// cmx = max(cmx,dis[u]);
dajk(u);
}
ll rez = -1;
for(ll i = 1;i<=n;i++){
if(!upd[i]) continue;
if(rez==-1||dis[i]<dis[rez]) rez = i;
}
// ceri(dis,1,n);
// ceri(upd,1,n);
// ceri(dis,1,n);
// cerr<<rez<<" "<<(rez==-1?-1:dis[rez])<<endl;
if(rez==-1){
if(u==0) return;
senduj(0);
return;
}
upd[rez] = 0;
senduj(rez);
cmx = max(cmx,dis[rez]);
}
std::vector<int> Answer() {
vector<ll> ans;
for(ll i = 1;i<=n;i++) ans.pb(dis[i]);
for(ll i = 1;i<=n;i++) assert(dis[i]!=llinf);
// cer(ans);
return ans;
}
#include "Baijan.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define llinf 1000000000 // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
using ld = long double;
using ll = int;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld,ld>;
static const ll maxn = 2005;
static const ll lgn = 11;
static const ll lgd = 9;
static ll n;
static vector<pll> g[maxn];
static ll dis[maxn];
static bool upd[maxn];
static void dajk(ll u){
if(u==0) return;
priority_queue<pll> pq;
pq.push({-dis[u],u});
while(si(pq)){
ll d = -pq.top().fi,u = pq.top().sc; pq.pop();
if(dis[u]!=d) continue;
for(pll p : g[u]){
ll s = p.fi,w = p.sc;
if(dis[s]>dis[u]+w){
dis[s] = dis[u] + w;
pq.push({-dis[s],s});
upd[s] = 1;
}
}
}
}
static ll cmx = 0;
static void senduj(ll u){
if(u==0){
for(ll i = 0;i<lgn+lgd;i++) SendB(0);
return;
}
// cerr<<"SB: ";
// dbg(u);
for(ll j = 0;j<lgn;j++){
if((1<<j)&u) SendB(1);
else SendB(0);
}
ll disu = dis[u]-cmx;
for(ll j = 0;j<lgd;j++){
if((1<<j)&disu) SendB(1);
else SendB(0);
}
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
n = N;
for(ll i = 0;i<B;i++){
ll x = S[i],y = T[i],w = D[i];
x++; y++;
g[x].pb({y,w});
g[y].pb({x,w});
}
for(ll i = 1;i<=n;i++) dis[i] = llinf;
dis[1] = 0;
dajk(1);
// ceri(dis,1,n);
}
static ll cnt = 0;
static vector<bool> cur;
static pll conv(){
ll u = 0,disu = 0;
for(ll j = 0;j<lgn;j++){
u+=(1<<j)*cur[j];
}
for(ll j = lgn;j<lgn+lgd;j++){
disu+=(1<<(j-lgn))*cur[j];
}
return {u,disu};
}
void ReceiveB(bool y) {
cur.pb(y); cnt++;
if(cnt!=lgn+lgd) return;
pll p = conv();
cur.clear();
cnt = 0;
ll u = p.fi;
// cerr<<"B: "<<u<< " "<<cmx<<endl;
if(u){
dis[u] = min(dis[u],cmx+p.sc);
cmx = max(cmx,dis[u]);
//cmx = max(cmx,dis[u]);
dajk(u);
}
ll rez = -1;
for(ll i = 1;i<=n;i++){
if(!upd[i]) continue;
if(rez==-1||dis[i]<dis[rez]) rez = i;
}
// cerr<<"B: "<<endl;
// ceri(dis,1,n);
// ceri(upd,1,n);
// dbg(rez);
// cerr<<rez<<" "<<(rez==-1?-1:dis[rez])<<endl;
if(rez==-1){
if(u==0) return;
senduj(0);
return;
}
// cerr<<dis[rez]-cmx<<endl;
upd[rez] = 0;
senduj(rez);
cmx = max(cmx,dis[rez]);
}
