// ---------------- A ----------------

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;

#ifndef LOCAL
#include"Azer.h"
#endif

namespace A{
  int n,m,U[2]={11,9},ty,num,V[2],v,lst,now,dis[3010];
  bool vis[3010],shit;
  vector<pair<int,int>>G[3010];
  void S(int x,int t){
    // printf("A send: x=%d\n",x);
    drep(i,t-1,0)SendA(x>>i&1);
  }
  bool ins(bool x){
    V[ty]=V[ty]<<1|x;
    return --num;
  }
  void sty(int nt){
    V[ty=nt]=0;
    num=U[nt];
  }
  void upd(int u,int d){
    // printf("A upd: u=%d,d=%d\n",u,d);
    lst=dis[u]=d,vis[u]=1;
    for (auto [v,w]:G[u])
      if (dis[v]>w+d)dis[v]=w+d;
    v=n;
    rep(i,1,n)if (!vis[i]&&dis[v]>dis[i])v=i;
    now=dis[v];
    sty(1),S(now-lst,U[1]);
    // printf("A get v=%d\n",v);
  }
  void InitA(int _n,int _m,vector<int>u,vector<int>v,vector<int>w){
    if (shit)assert(0);
    shit=1;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    n=_n,m=_m;
    rep(i,0,m-1){
      G[u[i]].push_back({v[i],w[i]});
      G[v[i]].push_back({u[i],w[i]});
    }
    upd(0,0);
  }
  void ReceiveA(bool x){
    if (ins(x))return ;
    if (!ty)upd(V[0],V[1]+lst);
    else{
      // printf("A rec w=%d\n",V[1]);
      if (V[1]+lst>=now){ // change to > when B
        // puts("A win now");
        if (v!=n){
          S(v,U[0]);
          upd(v,now);
        }
      }else
        sty(0);
    }
  }
  vector<int>Answer(){
    vector<int>res(n);
    rep(i,0,n-1)res[i]=dis[i];
    return res;
  }
}

void InitA(int _n,int _m,vector<int>u,vector<int>v,vector<int>w){A::InitA(_n,_m,u,v,w);}
void ReceiveA(bool x){A::ReceiveA(x);}
vector<int>Answer(){return A::Answer();}

// ---------------- B ----------------

#ifndef LOCAL
#include"Baijan.h"
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
#endif

namespace B{
  int n,m,U[2]={11,9},ty,num,V[2],v,lst,now,dis[3010];
  bool vis[3010];
  vector<pair<int,int>>G[3010];
  void S(int x,int t){
    // printf("B send: x=%d\n",x);
    drep(i,t-1,0)SendB(x>>i&1);
  }
  bool ins(bool x){
    V[ty]=V[ty]<<1|x;
    return --num;
  }
  void sty(int nt){
    V[ty=nt]=0;
    num=U[nt];
  }
  void upd(int u,int d){
    // printf("B upd: u=%d,d=%d\n",u,d);
    lst=dis[u]=d,vis[u]=1;
    for (auto [v,w]:G[u])
      if (dis[v]>w+d)dis[v]=w+d;
    v=n;
    rep(i,1,n)if (!vis[i]&&dis[v]>dis[i])v=i;
    now=dis[v];
    sty(1),S(now-lst,U[1]);
    // printf("B get v=%d\n",v);
  }
  void InitB(int _n,int _m,vector<int>u,vector<int>v,vector<int>w){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    n=_n,m=_m;
    rep(i,0,m-1){
      G[u[i]].push_back({v[i],w[i]});
      G[v[i]].push_back({u[i],w[i]});
    }
    upd(0,0);
  }
  void ReceiveB(bool x){
    if (ins(x))return ;
    if (!ty)upd(V[0],V[1]);
    else{
      // printf("B rec w=%d\n",V[1]);
      if (V[1]+lst>now){ // change to >= when A
        // puts("B win now");
        if (v!=n){
          S(v,U[0]);
          upd(v,now);
        }
      }else
        sty(0);
    }
  }
}

void InitB(int _n,int _m,vector<int>u,vector<int>v,vector<int>w){B::InitB(_n,_m,u,v,w);}
void ReceiveB(bool x){B::ReceiveB(x);}