#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace a {
int N;
vector<vector<pair<int, int>>> adj;
priority_queue<pair<int, int>> pq;
vector<int> d;
vector<int> done;
int max_until_now = 0;
bool receive_length = 0;
int cnt_length;
int length, length_a;
int pos, cnt_pos;
int a;
void send_nude(int du, int u) {
// cerr << du << ' ' << u << '\n';
length_a = du - max_until_now;
a = u;
// cerr << "now sending length " << length_a << " from a to b!\n";
for (int i = 0; i < 9; i++) SendA(length_a >> i & 1);
receive_length = 1;
cnt_length = length = 0;
}
void try_next() {
while (pq.size()) {
auto [du, u] = pq.top();
// cerr << "pq : " << du << ' ' << u << '\n';
if (done[u] == 0) {
send_nude(-du, u);
return;
}
pq.pop();
// cerr << d[u] << '\n';
if (-du != d[u]) continue;
max_until_now = -du;
for (auto [v, w] : adj[u]) {
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
pq.emplace(-d[v], v);
}
}
}
for (int i = 0; i < N; i++) {
if (done[i] == 0) {
send_nude(max_until_now + 511, 0);
return;
}
}
}
} // namespace a
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
a::N = N;
a::adj.resize(N);
a::d.assign(N, 1e9);
a::done.assign(N, 0);
for (int i = 0; i < A; i++) a::adj[U[i]].emplace_back(V[i], C[i]);
for (int i = 0; i < A; i++) a::adj[V[i]].emplace_back(U[i], C[i]);
a::pq.emplace(0, 0);
a::d[0] = 0;
a::done[0] = 1;
a::try_next();
}
void ReceiveA(bool x) {
if (a::receive_length) {
a::length |= x << a::cnt_length;
a::cnt_length++;
if (a::cnt_length == 9) {
// cerr << "now receiving length " << a::length << " from b to a\n";
if (a::length < a::length_a) {
a::length += a::max_until_now;
a::pos = a::cnt_pos = 0;
a::receive_length = 0;
} else {
// cerr << "now sending pos " << a::a << " from a to b!\n";
for (int i = 0; i < 11; i++) SendA(a::a >> i & 1);
a::done[a::a] = 1;
a::try_next();
}
}
} else {
a::pos |= x << a::cnt_pos;
a::cnt_pos++;
if (a::cnt_pos == 11) {
// cerr << a::max_until_now << '\n';
// cerr << "now receiving pos " << a::pos << " from b to a!\n";
a::done[a::pos] = 1;
a::d[a::pos] = a::length;
a::pq.emplace(-a::length, a::pos);
a::try_next();
}
}
}
std::vector<int> Answer() {
return a::d;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace b {
int N;
int x = 0;
vector<vector<pair<int, int>>> adj;
priority_queue<pair<int, int>> pq;
vector<int> d;
vector<int> done;
int length, cnt_length;
bool receive_length;
int length_b;
int max_until_now;
int pos, cnt_pos;
void send_nude(int du, int u) {
// cerr << "send_nude on b: " << du << ' ' << u << '\n';
int length_b = du - max_until_now;
// cerr << "now sending " << length_b << " from b to a!\n";
for (int i = 0; i < 9; i++) SendB(length_b >> i & 1);
if (length_b < length) {
for (int i = 0; i < 11; i++) SendB(u >> i & 1);
done[u] = 1;
length = cnt_length = 0;
receive_length = 1;
} else {
receive_length = 0;
pos = 0, cnt_pos = 0;
}
}
} // namespace b
void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
b::N = N;
b::adj.resize(N);
b::d.assign(N, 1e9);
b::done.assign(N, 0);
for (int i = 0; i < B; i++) b::adj[S[i]].emplace_back(T[i], D[i]);
for (int i = 0; i < B; i++) b::adj[T[i]].emplace_back(S[i], D[i]);
b::pq.emplace(0, 0);
b::d[0] = 0;
b::done[0] = 1;
b::max_until_now = 0;
b::receive_length = 1;
b::length = b::cnt_length = 0;
}
void ReceiveB(bool y) {
if (b::receive_length) {
b::length |= y << b::cnt_length;
b::cnt_length++;
if (b::cnt_length == 9) {
bool ok = 1;
for (int i = 0; i < b::N; i++) ok &= b::done[i];
// cerr << "now receiving length " << b::length << " from a to b\n";
while (b::pq.size()) {
auto [du, u] = b::pq.top();
if (b::done[u] == 0) {
b::send_nude(-du, u);
ok = 1;
break;
}
b::pq.pop();
if (-du != b::d[u]) continue;
b::max_until_now = -du;
for (auto&& [v, w] : b::adj[u]) {
if (b::d[v] > b::d[u] + w) {
b::d[v] = b::d[u] + w;
b::pq.emplace(-b::d[v], v);
}
}
}
if (!ok) b::send_nude(b::max_until_now + 511, 0);
}
} else {
b::pos |= y << b::cnt_pos;
b::cnt_pos++;
if (b::cnt_pos == 11) {
// cerr << "now receiving pos " << b::pos << " from a to b!\n";
b::d[b::pos] = b::length + b::max_until_now;
b::max_until_now = b::d[b::pos];
b::pq.emplace(-b::d[b::pos], b::pos);
b::done[b::pos] = 1;
b::receive_length = 1;
b::cnt_length = b::length = 0;
}
}
}
