#include"Azer.h"
#include<bits/stdc++.h>
#define L(i,s,t) for(int i=(s);i<=(t);++i)
#define R(i,s,t) for(int i=(s);i>=(t);--i)
#define T(i,s,t) for(int i=(s);i< (t);++i)
#define iV inline void
#define iI inline int
#define iB inline bool
#define vc vector
#define vi vc<int>
#define eb emplace_back
#define sz(x) (int)(x).size()
#define I(x) (1<<(x))
#define all(x) x.begin(),x.end()
using namespace std;
namespace {
    const int N=2003,M=1e6+3,inf=1e9;
    int n,Lg[N],h[N],tot;
    int dis,ide,cur,typ,Ids,Ide;
    int las;//上次的值
    vi p,d;//存储剩余点集
    struct edge{int v,w,nxt;}e[M];
    iV add(int u,int v,int w) {e[++tot]={v,w,h[u]},h[u]=tot;}
    iV lnk(int u,int v,int w) {add(u,v,w),add(v,u,w);}
    iB chn(int &x,int y) {return x>y?(x=y,1):0;}
    iV upd(int x,int y) {
        d[x]=las=las+y,p.erase(find(all(p),x));
        if(p.empty()) return;
        for(int i=h[x];i;i=e[i].nxt) chn(d[e[i].v],y+e[i].w);
        dis=inf,ide=typ=Ids=Ide=0,cur=8;
        T(i,0,sz(p)) if(chn(dis,d[p[i]]-y)) ide=i;
        R(i,8,0) SendA(dis>>i&1);
    }
}
void InitA(int Tn,int A,vi U,vi V,vi C) {
    n=Tn,d.resize(n);
    L(i,2,n) Lg[i]=Lg[i>>1]+1;
    T(i,0,n) p.eb(i),d[i]=inf;
    T(i,0,A) lnk(U[i],V[i],C[i]);
    upd(0,0);
}
void ReceiveA(bool x) {
    if(!typ) {
        Ids|=x<<cur--;
        if(cur<0) {
            if(Ids>dis) return upd(p[ide],dis);
            cur=Lg[sz(p)-1],typ=0;
        }
    }
    else {
        Ide|=x<<cur--;
        if(cur<0) return upd(p[Ide],Ids);
    }
}
vi Answer() {return d;}

#include "Baijan.h"
#include <bits/stdc++.h>
#define L(i,s,t) for(int i=(s);i<=(t);++i)
#define R(i,s,t) for(int i=(s);i>=(t);--i)
#define T(i,s,t) for(int i=(s);i< (t);++i)
#define iV inline void
#define iI inline int
#define iB inline bool
#define vc vector
#define vi vc<int>
#define eb emplace_back
#define sz(x) (int)(x).size()
#define I(x) (1<<(x))
#define all(x) x.begin(),x.end()
using namespace std;
namespace {
    const int N=2003,M=1e6+3,inf=1e9;
    int n,Lg[N],h[N],tot;
    int dis,ide,cur,typ,Ids,Ide,las;
    vi p,d;
    struct edge{int v,w,nxt;}e[M];
    iV add(int u,int v,int w) {e[++tot]={v,w,h[u]},h[u]=tot;}
    iV lnk(int u,int v,int w) {add(u,v,w),add(v,u,w);}
    iB chn(int &x,int y) {return x>y?(x=y,1):0;}
    iV upd(int x,int y) {
        d[x]=las=las+y,p.erase(find(all(p),x));
        if(p.empty()) return;
        for(int i=h[x];i;i=e[i].nxt) chn(d[e[i].v],y+e[i].w);
        dis=inf,ide=typ=Ids=Ide=0,cur=8;
        T(i,0,sz(p)) if(chn(dis,d[p[i]]-y)) ide=i;
        R(i,8,0) SendB(dis>>i&1);
    }
}
void InitB(int Tn,int A,vi U,vi V,vi C) {
    n=Tn,d.resize(n);
    L(i,2,n) Lg[i]=Lg[i>>1]+1;
    T(i,0,n) p.eb(i),d[i]=inf;
    T(i,0,A) lnk(U[i],V[i],C[i]);
    upd(0,0);
}
void ReceiveB(bool x) {
    if(!typ) {
        Ids|=x<<cur--;
        if(cur<0) {
            if(Ids>dis) return upd(p[ide],dis);
            cur=Lg[sz(p)-1],typ=0;
        }
    }
    else {
        Ide|=x<<cur--;
        if(cur<0) return upd(p[Ide],Ids);
    }
}