#include "Azer.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
using namespace std;
namespace {
int n,dist[2005],fix[2005];
vector<pair<int,int>> g[2005];
priority_queue<pair<int,int>> q;
int cur,w,idx;
int w2,idx2,num2;
bool MM;
int cnt;
}
void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
n=N;
for (int i=0; i<A; i++) {
g[U[i]].pb({V[i],C[i]});
g[V[i]].pb({U[i],C[i]});
}
for (int i=0; i<n; i++) {
dist[i]=1000005; fix[i]=0;
g[i].pb({n,1000005});
}
dist[n]=1000005; fix[n]=0;
dist[0]=0; cnt=1;
q.push({0,0}); q.push({-dist[n],n});
fix[0]=1;
priority_queue<pii> q2; q2.push({0,0});
vector<int> f(n,0);
while (!q2.empty()) {
int v=q2.top().s; q2.pop();
if (f[v]) continue;
q.push({-dist[v],v});
f[v]=1;
for (auto L:g[v]) {
int u=L.f,wei=L.s;
if (dist[u]>dist[v]+wei) {
dist[u]=dist[v]+wei;
q2.push({-dist[u],u});
}
}
}
while (q.top().s<n && fix[q.top().s]) q.pop();
cur=q.top().s; w=dist[cur]; idx=19; w2=0; idx2=19; MM=0; num2=0;
while (idx>=0) {
SendA(w&(1<<idx)); idx--;
}
}
void ReceiveA(bool x) {
if (MM==0) {
cnt++;
if (x) w2+=(1<<idx2);
idx2--;
if (idx2==-1) {
if (w==w2 && w>1000000) {
return;
}
if (w<=w2) {
idx=10;
fix[cur]=1;
while (idx>=0) {
SendA(cur&(1<<idx)); idx--;
}
if (cnt==n) return;
while (q.top().s<n && fix[q.top().s]) q.pop();
cur=q.top().s; w=dist[cur]; idx=19; w2=0; idx2=19; MM=0;
while (idx>=0) {
SendA(w&(1<<idx)); idx--;
}
}
else {
MM=1; idx2=10; num2=0;
}
}
}
else {
if (x) num2+=(1<<idx2);
idx2--;
if (idx2==-1) {
dist[num2]=w2; fix[num2]=1;
priority_queue<pii> q2; q2.push({-dist[num2],num2});
vector<int> f(n,0);
while (!q2.empty()) {
int v=q2.top().s; q2.pop();
if (f[v]) continue;
f[v]=1;
for (auto L:g[v]) {
int u=L.f,wei=L.s;
if (dist[u]>dist[v]+wei) {
dist[u]=dist[v]+wei;
q2.push({-dist[u],u});
q.push({-dist[u],u});
}
}
}
if (cnt==n) return;
while (q.top().s<n && fix[q.top().s]) q.pop();
cur=q.top().s; w=dist[cur]; idx=19; w2=0; idx2=19; MM=0;
while (idx>=0) {
SendA(w&(1<<idx)); idx--;
}
}
}
}
vector<int> Answer() {
vector<int> ans(n);
for (int k=0; k<n; k++) {
ans[k]=dist[k];
}
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
using namespace std;
namespace {
int nn,distt[2005],fixx[2005];
vector<pair<int,int>> gg[2005];
priority_queue<pair<int,int>> qq;
int curr,ww,idxx;
int w22,idx22,num22;
bool MMM;
int cntt;
}
void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
nn=N;
for (int i=0; i<B; i++) {
gg[S[i]].pb({T[i],D[i]});
gg[T[i]].pb({S[i],D[i]});
}
for (int i=0; i<nn; i++) {
distt[i]=1000005; fixx[i]=0;
gg[i].pb({nn,1000005});
}
distt[nn]=1000005; fixx[nn]=0;
distt[0]=0; cntt=1;
qq.push({0,0}); qq.push({-distt[nn],nn});
fixx[0]=1;
priority_queue<pii> q2; q2.push({0,0});
vector<int> f(nn,0);
while (!q2.empty()) {
int v=q2.top().s; q2.pop();
if (f[v]) continue;
f[v]=1;
for (auto L:gg[v]) {
int u=L.f,wei=L.s;
if (distt[u]>distt[v]+wei) {
distt[u]=distt[v]+wei;
q2.push({-distt[u],u});
qq.push({-distt[u],u});
}
}
}
idxx=19; w22=0; idx22=19; MMM=0; num22=0;
}
void ReceiveB(bool y) {
if (MMM==0) {
if (y) w22+=(1<<idx22);
idx22--;
if (idx22==-1) {
while (qq.top().s<nn && fixx[qq.top().s]) qq.pop();
curr=qq.top().s; ww=distt[curr];
if (ww<w22) {
fixx[curr]=1;
idxx=19; w22=0; idx22=19; MMM=0;
while (idxx>=0) {
SendB(ww&(1<<idxx)); idxx--;
}
idxx=10;
while (idxx>=0) {
SendB(curr&(1<<idxx)); idxx--;
}
cntt++;
idxx=19; w22=0; idx22=19; MMM=0;
}
else {
while (idxx>=0) {
SendB(ww&(1<<idxx)); idxx--;
}
MMM=1; idx22=10; num22=0;
}
}
}
else {
if (y) num22+=(1<<idx22);
idx22--;
if (idx22==-1) {
distt[num22]=w22; fixx[num22]=1;
priority_queue<pii> q2; q2.push({-distt[num22],num22});
vector<int> f(nn,0);
while (!q2.empty()) {
int v=q2.top().s; q2.pop();
if (f[v]) continue;
f[v]=1;
for (auto L:gg[v]) {
int u=L.f,wei=L.s;
if (distt[u]>distt[v]+wei) {
distt[u]=distt[v]+wei;
q2.push({-distt[u],u});
qq.push({-distt[u],u});
}
}
}
idxx=19; w22=0; idx22=19; MMM=0;
}
}
}
