#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
namespace {
const int inf = 1e6+1;
vector<pii> adj[2005];
priority_queue<pii,vector<pii>,greater<pii>> pq;
int d[2005],n,m0,cnt,v0,w0,prv;
pii prv2;
bitset<2005> vis;
void send(bool x){ return SendA(x); }
void send(int x,int m){ while(m--) send(x&1), x>>=1; }
void send(pii x){
if(x==prv2) return void(send(1));
prv2=x;
send(0);
send(x.s,11);
send(min(x.f-prv,511),9);
}
void play(){
auto [w,u]=pq.top(); pq.pop();
if(u==n) return;
if(vis[u]) return play();
vis[u]=1;
for(auto &[v,vw]:adj[u]) if(d[v]>w+vw) pq.emplace(d[v]=w+vw,v);
while(!pq.empty() && pq.top().s!=n && vis[pq.top().s]) pq.pop();
prv=w;
send(pq.top());
}
} // namespace
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
n=N;
for(int i=0;i<A;++i) adj[U[i]].eb(V[i],C[i]), adj[V[i]].eb(U[i],C[i]);
m0=cnt=0;
prv2={-1,0};
fill(d,d+N,inf);
pq.emplace(inf,N);
pq.emplace(d[0]=0,0);
play();
}
void ReceiveA(bool x) {
if(cnt==0){
if(x){
m0=cnt=0;
play();
return;
}
}
else if(cnt<12) m0 |= x<<cnt-1;
else m0 |= x<<cnt-12;
++cnt;
if(cnt==12) v0=m0, m0=0;
else if(cnt==21){
w0=(m0==511 ? inf : m0+prv);
m0=cnt=0;
if(v0!=n && d[v0]>w0) pq.emplace(d[v0]=w0,v0);
play();
}
}
std::vector<int> Answer() {
vector<int> ans(n);
for(int i=0;i<n;++i) ans[i]=d[i];
return ans;
}
#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define eb emplace_back
#define sz(x) (int)x.size()
#define f first
#define s second
namespace {
const int inf=1e6+1;
vector<pii> adj[2005];
priority_queue<pii,vector<pii>,greater<pii>> pq;
int d[2005],n,m0,cnt,v0,w0,prv;
pii prv2;
bitset<2005> vis;
void send(bool x){ return SendB(x); }
void send(int x,int m){ while(m--) send(x&1), x>>=1; }
void send(pii x){
if(x==prv2) return void(send(1));
prv2=x;
send(0);
send(x.s,11);
send(min(x.f-prv,511),9);
}
void play(){
auto [w,u]=pq.top(); pq.pop();
if(u==n) return;
if(vis[u]) return play();
vis[u]=1;
for(auto &[v,vw]:adj[u]) if(d[v]>w+vw) pq.emplace(d[v]=w+vw,v);
while(!pq.empty() && pq.top().s!=n && vis[pq.top().s]) pq.pop();
prv=w;
send(pq.top());
}
} // namespace
void InitB(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
n=N;
for(int i=0;i<A;++i) adj[U[i]].eb(V[i],C[i]), adj[V[i]].eb(U[i],C[i]);
m0=cnt=0;
prv2={-1,0};
fill(d,d+N,inf);
pq.emplace(inf,N);
pq.emplace(d[0]=0,0);
play();
}
void ReceiveB(bool x) {
if(cnt==0){
if(x){
m0=cnt=0;
play();
return;
}
}
else if(cnt<12) m0 |= x<<cnt-1;
else m0 |= x<<cnt-12;
++cnt;
if(cnt==12) v0=m0, m0=0;
else if(cnt==21){
w0=(m0==511 ? inf : m0+prv);
m0=cnt=0;
if(v0!=n && d[v0]>w0) pq.emplace(d[v0]=w0,v0);
play();
}
}
