#include "Azer.h"
#include <cstdlib>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;

namespace A{
const int MAXN=2e3+10,MAXM=1e6+10;
int to[MAXM],nxt[MAXM],head[MAXN],val[MAXM],tot;
int o=1,n,r=11,tmp,dis[MAXN],pre,cnt,MIN,pos;bool vis[MAXN];

inline void add(int x,int y,int z)
    {to[++tot]=y,nxt[tot]=head[x],val[head[x]=tot]=z;}

inline void upd(int x,int D)
{
    ++cnt,pre=dis[x]=D,vis[x]=true;
    for(int i=head[x];i;i=nxt[i])
        {int y=to[i];dis[y]=min(dis[y],dis[x]+val[i]);}
}

inline void find()
{
    MIN=1e9;for(int i=0;i<n;++i)
        if(!vis[i]&&dis[i]<MIN)
            MIN=dis[i],pos=i;
}

inline void Send(int k,int x)
    {for(int i=k-1;~i;--i) SendA((x>>i)&1);}

inline void send(bool flag)
    {find();flag?Send(9,min(MIN-pre,511)):Send(11,pos);}

inline void dij()
    {find();upd(pos,MIN);}

void Init(int n,int m,vector<int> x,vector<int> y,vector<int> z)
{
    A::n=n,o=1;
    for(int i=1;i<n;++i) dis[i]=(1<<20)-1;
    for(int i=0;i<m;++i) add(x[i],y[i],z[i]),add(y[i],x[i],z[i]);
}

void Receive(bool f)
{
    tmp=tmp<<1|f;if(--r) return ;
    if(o==1)
    {
        // cout<<'A'<<o<<' '<<tmp<<'\n';
        int x=tmp;tmp=0,upd(x,pre);
        if(cnt==n) return ;
        send(1),o=3,r=9;
    }
    else if(o==2)
    {
        // cout<<'A'<<o<<' '<<tmp<<'\n';
        int D=tmp;tmp=0;find(),send(1);
        if(D<=MIN-pre) pre+=D,o=1,r=11;
        else upd(pos,MIN),Send(11,pos),o=2,r=9;
    }
    else
    {
        // cout<<'A'<<o<<' '<<tmp<<'\n';
        int D=tmp;tmp=0;find();
        if(D<MIN-pre) pre+=D,o=1,r=11;
        else upd(pos,MIN),Send(11,pos),o=2,r=9;
    }
}

};

void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C)
{
    A::Init(N, A, U, V, C);
}

void ReceiveA(bool x)
{
    exit(-1);
    A::Receive(x);
}

vector<int> Answer(){vector<int> ans(A::n);for(int i=0;i<A::n;++i) ans[i]=A::dis[i];return ans;}

#include "Baijan.h"
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;

namespace B{
const int MAXN=2e3+10,MAXM=1e6+10;
int to[MAXM],nxt[MAXM],head[MAXN],val[MAXM],tot;
int o=2,n,r=9,tmp,dis[MAXN],pre,cnt,MIN,pos;bool vis[MAXN];

inline void add(int x,int y,int z)
    {to[++tot]=y,nxt[tot]=head[x],val[head[x]=tot]=z;}

inline void upd(int x,int D)
{
    ++cnt,pre=dis[x]=D,vis[x]=true;
    for(int i=head[x];i;i=nxt[i])
        {int y=to[i];dis[y]=min(dis[y],dis[x]+val[i]);}
}

inline void find()
{
    MIN=1e9;for(int i=0;i<n;++i)
        if(!vis[i]&&dis[i]<MIN)
            MIN=dis[i],pos=i;
}

inline void Send(int k,int x)
    {exit(-1);for(int i=k-1;~i;--i) SendB((x>>i)&1);}

inline void send(bool flag)
    {find();flag?Send(9,min(MIN-pre,511)):Send(11,pos);}

inline void dij()
    {find();upd(pos,MIN);}

void Init(int n,int m,vector<int> x,vector<int> y,vector<int> z)
{
    B::n=n,o=2;
    for(int i=1;i<n;++i) dis[i]=(1<<20)-1;
    for(int i=0;i<m;++i) add(x[i],y[i],z[i]),add(y[i],x[i],z[i]);
    upd(0,0),Send(11,0);
}

void Receive(bool f)
{
    tmp=tmp<<1|f;if(--r) return ;
    if(o==1)
    {
        // cout<<'B'<<o<<' '<<tmp<<'\n';
        int x=tmp;tmp=0,upd(x,pre);
        if(cnt==n) return ;
        send(1),o=3,r=9;
    }
    else if(o==2)
    {
        // cout<<'B'<<o<<' '<<tmp<<'\n';
        int D=tmp;tmp=0;find(),send(1);
        if(D<=MIN-pre) pre+=D,o=1,r=11;
        else upd(pos,MIN),Send(11,pos),o=2,r=9;
    }
    else
    {
        // cout<<'B'<<o<<' '<<tmp<<'\n';
        int D=tmp;tmp=0;find();
        if(D<MIN-pre) pre+=D,o=1,r=11;
        else upd(pos,MIN),Send(11,pos),o=2,r=9;
    }
}

};

void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D)
{
    B::Init(N, B, S, T, D);
}

void ReceiveB(bool y)
{
    B::Receive(y);
}