#include "Azer.h"
#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
namespace {
bool enableDebug = 0;
const int inf = (1<<25)-1;
const int maxn = 1<<11;
const int maxsz = 12;
int N, cur = 0;
vi dist;
vector<vector<pi>> adj;
vi arr;
int cnt;
multiset<pi> st;
int curSize = maxsz;
int dA, vA, dB, vB;
int mxDist = 0;
void sendIntA(int x, int sz = maxsz) {
if (enableDebug) cerr << "A is sending: " << x << endl;
x = min(x, (1<<20)-1);
for (int i = 0; i < sz; i++) SendA(x & (1<<i));
}
} // namespace
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
::N = N;
mxDist = 0;
st.insert({0, 0});
dA = 0;
vA = 0;
dB = -1;
vB = -1;
dist.assign(N, inf);
dist[0] = 0;
adj.assign(N, vector<pi>());
arr.clear();
cnt = 0;
for (int i = 0; i < A; i++) {
adj[U[i]].push_back(make_pair(V[i], C[i]));
adj[V[i]].push_back(make_pair(U[i], C[i]));
}
sendIntA(0);
}
void tryEnd() {
for (int v = 0; v < N; v++) {
if (dist[v] == inf) {
sendIntA(inf - mxDist);
dA = inf;
vA = v;
st.insert({inf, v});
return;
}
}
}
void relax(int v) {
mxDist = max(mxDist, dist[v]);
for (pi p : adj[v]) {
int to, w;
tie(to, w) = p;
if (dist[v] + w > dist[to]) continue;
st.erase({dist[to], to});
dist[to] = min(dist[to], dist[v] + w);
st.insert({dist[to], to});
}
}
void readInt() {
if (enableDebug) cerr << "A has received: " << cur << endl;
if (dB == -1) {
dB = cur + mxDist;
if (dB >= dA) {
st.erase(st.begin());
sendIntA(vA);
relax(vA);
dB = -1;
vB = -1;
if (st.empty()) { tryEnd(); return; }
tie(dA, vA) = *st.begin();
sendIntA(dA - mxDist);
}
}
else {
vB = cur;
st.erase({dist[vB], vB});
dist[vB] = dB;
relax(vB);
dB = -1;
vB = -1;
if (st.empty()) { tryEnd(); return; }
tie(dA, vA) = *st.begin();
sendIntA(dA - mxDist);
}
}
void ReceiveA(bool x) {
cur = cur + ((1<<cnt) * x);
cnt++;
if (cnt == curSize) {
readInt();
cnt = cur = 0;
}
}
std::vector<int> Answer() {
return dist;
}
#include "Baijan.h"
#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
namespace b {
bool enableDebug = 0;
const int inf = (1<<25)-1;
const int maxn = 1<<11;
const int maxsz = 11;
int N, cur = 0;
vi dist;
vector<vector<pi>> adj;
vi arr;
int cnt;
multiset<pi> st;
int curSize = maxsz;
int dA, vA, dB, vB;
int mxDist = 0;
void sendIntB(int x, int sz = maxsz) {
x = min(x, (1<<20)-1);
if (enableDebug) cerr << "B is sending: " << x << endl;
for (int i = 0; i < sz; i++) SendB(x & (1<<i));
}
void initB(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
N = N;
mxDist = 0;
st.insert({0, 0});
dA = -1;
vA = -1;
dB = 0;
vB = 0;
dist.assign(N, inf);
dist[0] = 0;
adj.assign(N, vector<pi>());
arr.clear();
cnt = 0;
for (int i = 0; i < A; i++) {
adj[U[i]].push_back(make_pair(V[i], C[i]));
adj[V[i]].push_back(make_pair(U[i], C[i]));
}
}
void relax(int v) {
mxDist = max(mxDist, dist[v]);
for (pi p : adj[v]) {
int to, w;
tie(to, w) = p;
if (dist[v] + w > dist[to]) continue;
st.erase({dist[to], to});
dist[to] = min(dist[to], dist[v] + w);
st.insert({dist[to], to});
}
}
void readInt() {
if (enableDebug) cerr << "B has received: " << cur << endl;
if (st.empty()) {
dB = inf;
}
if (dA == -1) {
dA = cur + mxDist;
sendIntB(dB - mxDist);
if (dA > dB) {
sendIntB(vB);
relax(vB);
st.erase(st.begin());
vA = -1;
dA = -1;
if (st.empty()) return;
tie(dB, vB) = *st.begin();
}
}
else {
vA = cur;
st.erase({dist[vA], vA});
dist[vA] = dA;
relax(vA);
dA = -1;
vA = -1;
if (st.empty()) return;
tie(dB, vB) = *st.begin();
}
}
void receiveB(bool x) {
cur = cur + ((1<<cnt) * x);
cnt++;
if (cnt == curSize) {
readInt();
cnt = cur = 0;
}
}
} // namespace
void InitB(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
b::initB(N, A, U, V, C);
}
void ReceiveB(bool x) {
b::receiveB(x);
}
