#include "Azer.h"
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef vector<int> vi;
const int N = 2005, L1 = 11, L2 = 9;
int cnt;
namespace Azer{bool vis[N];
	int n, U, dis[N], e[N][N], Ls, Lr = L2, cr, xr, lst, cn, ttp;
	void Send(int x){if ((cnt += x) > 58000) exit(1);
		for (int i = 0;i < Ls;i ++) SendA(x >> i & 1);
	}
	void update(int u){cn ++;
		for (int v = 1;v <= n;v ++) if (e[u][v])
		dis[v] = min(dis[v], dis[u] + e[u][v]);vis[u] = 1;
	}
	void senddis(){if (cn == n) return;U = 0, Ls = L2;
		for (int i = 1;i <= n;i ++)
		if (!vis[i] && (!U || dis[i] < dis[U])) U = i;
		Send(dis[U]);
	}
	void sendnod(){Ls = L1, Send(U);}
	void recvdis(int x){
		if (dis[U] <= x) ttp = -1, update(U), sendnod(), senddis();
		else Lr = L1, ttp = x;
	}
	void recvnod(int u){if (ttp != -1) dis[u] = ttp;update(u), Lr = L2, senddis();}
	void ReceiveA(bool x){
		xr |= x << cr, cr ++;
		if (cr == Lr){int tp = xr;
			if (Lr == L2){xr = cr = 0, recvdis(tp);return;}
			if (Lr == L1){xr = cr = 0, recvnod(tp);return;}
		}
	}
	void InitA(int nn, int m, vi uu, vi vv, vi ww){
		memset(dis, 0x3f, sizeof(dis)), dis[1] = 0;
		for (int i = 0;i < m;i ++){
			int u = uu[i] + 1, v = vv[i] + 1;
			e[u][v] = e[v][u] = ww[i];
		}n = nn, senddis();
	}
	vi Answer(){return vi(dis + 1, dis + n + 1);}
}
void InitA(int nn, int m, vi uu, vi vv, vi ww){Azer::InitA(nn, m, uu, vv, ww);}
void ReceiveA(bool x){Azer::ReceiveA(x);}
vi Answer(){return Azer::Answer();}

#include "Baijan.h"
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef vector<int> vi;
const int N = 2005, L1 = 11, L2 = 9;
int cnt;
namespace Baijan{bool vis[N];
	int n, U, dis[N], e[N][N], Ls, Lr = L2, cr, xr, lst, ttp;
	void Send(int x){if ((cnt += x) > 58000) exit(1);
		for (int i = 0;i < Ls;i ++) SendB(x >> i & 1);
	}
	void update(int u){
		for (int v = 1;v <= n;v ++) if (e[u][v])
		dis[v] = min(dis[v], dis[u] + e[u][v]);vis[u] = 1;
	}
	void senddis(){U = 0, Ls = L2;
		for (int i = 1;i <= n;i ++)
		if (!vis[i] && (!U || dis[i] < dis[U])) U = i;
		Send(dis[U]);
	}
	void sendnod(){Ls = L1, Send(U);}
	void recvdis(int x){senddis();
		if (dis[U] < x) ttp = -1, update(U), sendnod();
		else Lr = L1, ttp = x;
	}
	void recvnod(int u){if (ttp != -1) dis[u] = ttp;update(u), Lr = L2;}
	void ReceiveB(bool x){
		xr |= x << cr, cr ++;
		if (cr == Lr){int tp = xr;
			if (Lr == L2){xr = cr = 0, recvdis(tp);return;}
			if (Lr == L1){xr = cr = 0, recvnod(tp);return;}
		}
	}
	void InitB(int nn, int m, vi uu, vi vv, vi ww){
		memset(dis, 0x3f, sizeof(dis)), dis[1] = 0;
		for (int i = 0;i < m;i ++){
			int u = uu[i] + 1, v = vv[i] + 1;
			e[u][v] = e[v][u] = ww[i];
		}n = nn;
	}
}
void InitB(int nn, int m, vi uu, vi vv, vi ww){Baijan::InitB(nn, m, uu, vv, ww);}
void ReceiveB(bool x){Baijan::ReceiveB(x);}