#include "Azer.h"
#include <bits/stdc++.h>
using i64 = long long;
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr int inf = int(1E9);
namespace {
template<typename T>
bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
void send(int x, int c) {
for (int i = 0; i < c; ++i) {
SendA(x >> i & 1);
}
}
int N;
std::vector<int> dis;
std::vector<int> vis;
std::vector<bool> buffer;
std::vector<std::vector<std::pair<int, int>>> adj;
min_pq<std::pair<int, int>> pq;
int cnt;
int mode;
int sent;
int lst;
void update(int v) {
for (auto[u, w] : adj[v]) {
if (chmin(dis[u], dis[v] + w)) {
pq.emplace(dis[u], u);
}
}
}
void send_pq() {
cnt--;
if (cnt == 0) {
return;
}
while (true) {
if (pq.empty()) {
sent = 511;
send(sent, 9);
break;
}
auto[d, v] = pq.top();
if (dis[v] != d || vis[v]) {
pq.pop();
continue;
}
// std::cerr << "[AS: " << v << ' ' << d << "]\n";
sent = dis[v] - lst;
send(sent, 9);
break;
}
}
} // namespace
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
::N = N;
cnt = N;
adj.resize(N);
dis.resize(N, inf);
vis.resize(N, 0);
for (int i = 0; i < A; ++i) {
adj[U[i]].emplace_back(V[i], C[i]);
adj[V[i]].emplace_back(U[i], C[i]);
}
vis[0] = true;
dis[0] = 0;
update(0);
send_pq();
mode = false;
}
void ReceiveA(bool x) {
buffer.emplace_back(x);
if (mode) {
if (int(buffer.size()) == 11) {
int v = 0;
for (int i = 0; i < 11; ++i) {
v += buffer[i] << i;
}
dis[v] = lst;
vis[v] = true;
update(v);
send_pq();
buffer.clear();
mode = false;
}
} else {
if (int(buffer.size()) == 9) {
int c = 0;
for (int i = 0; i < 9; ++i) {
c += buffer[i] << i;
}
if (c >= sent) {
int v = pq.top().second;
pq.pop();
vis[v] = true;
lst += sent;
send(v, 11);
update(v);
send_pq();
mode = false;
} else {
sent = c;
lst += sent;
mode = true;
}
buffer.clear();
}
}
}
std::vector<int> Answer() {
return dis;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using i64 = long long;
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr int inf = int(1E9);
namespace {
template<typename T>
bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
void send(int x, int c) {
for (int i = 0; i < c; ++i) {
SendB(x >> i & 1);
}
}
int N;
std::vector<int> dis;
std::vector<int> vis;
std::vector<bool> buffer;
std::vector<std::vector<std::pair<int, int>>> adj;
min_pq<std::pair<int, int>> pq;
int cnt;
int mode;
int sent;
int lst;
void update(int v) {
for (auto[u, w] : adj[v]) {
if (chmin(dis[u], dis[v] + w)) {
pq.emplace(dis[u], u);
}
}
}
void send_pq() {
cnt--;
if (cnt == 0) {
return;
}
while (true) {
if (pq.empty()) {
sent = 511;
send(sent, 9);
break;
}
auto[d, v] = pq.top();
if (dis[v] != d || vis[v]) {
pq.pop();
continue;
}
// std::cerr << "[BS: " << v << ' ' << d << "]\n";
sent = dis[v] - lst;
send(sent, 9);
break;
}
}
} // namespace
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
std::vector<int> D) {
::N = N;
cnt = N;
adj.resize(N);
dis.resize(N, inf);
vis.resize(N, 0);
for (int i = 0; i < B; ++i) {
adj[S[i]].emplace_back(T[i], D[i]);
adj[T[i]].emplace_back(S[i], D[i]);
}
vis[0] = true;
dis[0] = 0;
update(0);
send_pq();
mode = false;
}
void ReceiveB(bool y) {
buffer.emplace_back(y);
if (mode) {
if (int(buffer.size()) == 11) {
int v = 0;
for (int i = 0; i < 11; ++i) {
v += buffer[i] << i;
}
dis[v] = lst;
vis[v] = true;
update(v);
send_pq();
buffer.clear();
mode = false;
}
} else {
if (int(buffer.size()) == 9) {
int c = 0;
for (int i = 0; i < 9; ++i) {
c += buffer[i] << i;
}
if (c > sent) {
int v = pq.top().second;
pq.pop();
vis[v] = true;
lst += sent;
send(v, 11);
update(v);
send_pq();
mode = false;
} else {
sent = c;
lst += sent;
mode = true;
}
buffer.clear();
}
}
}
