#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;
namespace A {
const int inf = 1e9;
int n, a;
vector<vector<pair<int, int> > > gr;
int mxD;
vector<int> d;
int cntDone = 0;
vector<bool> done;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
pair<int, int> cur{};
int dest = 9;
void ins(int u) { pq.emplace(d[u], u); }
int get() {
if (!sz(pq) ) return -1;
int ret = pq.top().second; pq.pop();
done[ret] = true;
mxD = d[ret];
++cntDone;
while (sz(pq) && done[pq.top().second]) pq.pop();
return ret;
}
int relaxingD;
void relax(int u) {
for (auto e : gr[u]) {
int v = e.first, w = e.second;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
ins(v);
}
}
}
void send(int val, int len) {
for (int i = 0; i < len; ++i) SendA( (val >> i) & 1);
}
}
void InitA(int N, int A, vector<int> U, vector<int> V,
vector<int> C) {
A::n = N;
A::a = A;
A::gr.assign(A::n, {} );
for (int i = 0; i < A::a; ++i) {
A::gr[ U[i] ].emplace_back(V[i], C[i]);
A::gr[ V[i] ].emplace_back(U[i], C[i]);
}
A::mxD = 0;
A::d.assign(A::n, A::inf); A::d[0] = 0;
A::done.assign(A::n, false);
A::ins(0);
A::send(0, 9);
}
void ReceiveA(bool x) {
A::cur.second |= (x << (A::cur.first++) );
if (A::cur.first < A::dest) return ;
if (A::dest == 9) {
if (A::cur.second == (1 << 9) - 1) {
int u = A::get();
A::send(u, 11);
A::relax(u);
if (sz(A::pq) ) {
int tmp = A::pq.top().first - A::mxD;
A::send(tmp, 9);
}
else A::send( (1 << 9) - 1, 9);
}
else {
A::relaxingD = A::cur.second;
A::dest = 11;
}
}
else {
int u = A::cur.second;
A::mxD = A::d[u] = A::mxD + A::relaxingD; A::done[u] = true;
while (sz(A::pq) && A::done[A::pq.top().second]) A::pq.pop();
A::relax(u);
++A::cntDone;
if (A::cntDone == A::n) return;
if (sz(A::pq) ) {
int tmp = A::pq.top().first - A::mxD;
A::send(tmp, 9);
}
else A::send( (1 << 9) - 1, 9);
A::dest = 9;
}
A::cur = {};
}
vector<int> Answer() { return A::d; }
#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;
namespace B{
const int inf = 1e9;
int n, b;
vector<vector<pair<int, int> > > gr;
int mxD;
vector<int> d;
int cntDone = 0;
vector<bool> done;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
pair<int, int> cur{};
int dest = 9;
void ins(int u) { pq.emplace(d[u], u); }
int get() {
if (!sz(pq) ) return -1;
int ret = pq.top().second; pq.pop();
done[ret] = true;
mxD = d[ret];
++cntDone;
while (sz(pq) && done[pq.top().second]) pq.pop();
return ret;
}
int relaxingD;
void relax(int u) {
for (auto e : gr[u]) {
int v = e.first, w = e.second;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
ins(v);
}
}
}
void send(int val, int len) {
for (int i = 0; i < len; ++i) SendB( (val >> i) & 1);
}
}
void InitB(int N, int B, vector<int> S, vector<int> T,
vector<int> D) {
B::n = N;
B::b = B;
B::gr.assign(B::n, {} );
for (int i = 0; i < B::b; ++i) {
B::gr[ S[i] ].emplace_back(T[i], D[i]);
B::gr[ T[i] ].emplace_back(S[i], D[i]);
}
B::mxD = 0;
B::d.assign(B::n, B::inf); B::d[0] = 0;
B::done.assign(B::n, false);
B::ins(0);
}
void ReceiveB(bool y) {
B::cur.second |= (y << (B::cur.first++) );
if (B::cur.first < B::dest) return ;
if (B::dest == 9) {
int tmp = (sz(B::pq) ? B::pq.top().first - B::mxD : (1 << 9) - 2);
if (tmp < B::cur.second) {
int u = B::get();
B::relax(u);
B::send(tmp, 9);
B::send(u, 11);
}
else {
B::relaxingD = B::cur.second;
B::send( (1 << 9) - 1, 9);
B::dest = 11;
}
}
else {
int u = B::cur.second;
B::mxD = B::d[u] = B::relaxingD + B::mxD; B::done[u] = true;
while (sz(B::pq) && B::done[B::pq.top().second]) B::pq.pop();
B::relax(u);
++B::cntDone;
if (B::cntDone == B::n) return;
B::dest = 9;
}
B::cur = {};
}
