#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = a; i <= b; ++i)
#define for_(i, a, b) for (int i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd int mid = (l + r) >> 1
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
#include "Azer.h"
#include <vector>

namespace A {

	int N;
	std::vector <int> dis;
	std::vector <int> vis;
	std::vector <std::vector <pii> > tu;

	int type, len, au, bu, ad, bd, last;

	void Upd (int u) {
		dis[u] = last;
		vis[u] = true;
		far (p, tu[u]) {
			int v = p.first, w = p.second;
			dis[v] = std::min (dis[v], dis[u] + w);
		}
		au = -1;
		_for (u, 0, N - 1) {
			if (!vis[u]) {
				if (au == -1 || dis[au] > dis[u])
					au = u;
			}
		}
		if (au == -1) return;
		ad = dis[au] - last;
		for_ (i, 8, 0) SendA ((ad >> i) & 1);
		bu = 0, bd = 0, type = 0, len = 9;
		return;
	}

	void InitA (int N, int A, std::vector <int> U, std::vector <int> V, std::vector <int> C) {
		A::N = N;
		dis.resize (N, 1e6);
		vis.resize (N, 0);
		tu.resize (N);
		_for (i, 0, A - 1) {
			tu[U[i]].emplace_back (V[i], C[i]);
			tu[V[i]].emplace_back (U[i], C[i]);
		}
		au = bu = ad = bd = 0;
		Upd (0);
		return;
	}

	void ReceiveA (bool x) {
		if (type) bu = bu << 1 | x;
		else bd = bd << 1 | x;
		if (!(--len)) {
			if (type) last += bd, Upd (bu);
			else {
				if (ad <= bd) {
					for_ (i, 10, 0) SendA ((au >> i) & 1);
					last += ad, Upd (au);
				}
				else type = 1, len = 11;
			}
		}
		return;
	}

}  // namespace A

void InitA (int N, int A, std::vector <int> U, std::vector <int> V, std::vector <int> C) { A::InitA (N, A, U, V, C); }
void ReceiveA (bool x) { A::ReceiveA (x); }
std::vector <int> Answer () { return A::dis; }

#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = a; i <= b; ++i)
#define for_(i, a, b) for (int i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd int mid = (l + r) >> 1
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
#include "Baijan.h"
#include <vector>

namespace B {

	int N;
	std::vector <int> dis;
	std::vector <int> vis;
	std::vector <std::vector <pii> > tu;

	int type, len, au, bu, ad, bd, last;

	void Upd (int u) {
		dis[u] = last;
		vis[u] = true;
		far (p, tu[u]) {
			int v = p.first, w = p.second;
			dis[v] = std::min (dis[v], dis[u] + w);
		}
		bu = -1;
		_for (u, 0, N - 1) {
			if (!vis[u]) {
				if (bu == -1 || dis[bu] > dis[u])
					bu = u;
			}
		}
		if (bu == -1) return;
		bd = dis[bu] - last;
		for_ (i, 8, 0) SendB ((bd >> i) & 1);
		au = 0, ad = 0, type = 0, len = 9;
		return;
	}

	void InitB (int N, int B, std::vector <int> S, std::vector <int> T, std::vector <int> C) {
		B::N = N;
		dis.resize (N, 1e6);
		vis.resize (N, 0);
		tu.resize (N);
		_for (i, 0, B - 1) {
			tu[S[i]].emplace_back (T[i], C[i]);
			tu[T[i]].emplace_back (S[i], C[i]);
		}
		au = bu = ad = bd = 0;
		Upd (0);
		return;
	}

	void ReceiveB (bool x) {
		if (type) au = au << 1 | x;
		else ad = ad << 1 | x;
		if (!(--len)) {
			if (type) last += ad, Upd (au);
			else {
				if (bd < ad) {
					for_ (i, 10, 0) SendB ((bu >> i) & 1);
					last += bd, Upd (bu);
				}
				else type = 1, len = 11;
			}
		}
		return;
	}

}  // namespace B

void InitB (int N, int B, std::vector <int> S, std::vector <int> T, std::vector <int> C) { B::InitB (N, B, S, T, C); }
void ReceiveB (bool x) { B::ReceiveB (x); }