#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
namespace {
const ll MAXN = 2E3+16, INF = (1<<20)-1;
int n;
int cou;
ll curU, curW;
priority_queue <pair <ll, ll> > pq;
vector <pair <ll, ll> > adj[MAXN];
bool vis[MAXN];
ll unex;
vll dis;
pair <ll, ll> getTop () {
while (pq.size() && vis[pq.top().second]) pq.pop();
if (pq.size()) return { -pq.top().first, pq.top().second };
return { INF, MAXN-4 };
}
void propTop () {
ll u = getTop().second; pq.pop();
assert(pq.size());
vis[u] = true; unex--;
for (auto [v, w] : adj[u]) {
if (dis[v] <= dis[u]+w) continue;
dis[v] = dis[u]+w;
pq.push({ -dis[v], v });
}
}
void mySend (ll x, ll bits) { for (ll i = 0; i < bits; i++) SendA(x>>i&1); }
void sendTop () {
mySend(getTop().first, 20);
mySend(getTop().second, 11);
}
void readAll () {
if (curW < getTop().first) { // other wins, inserts in current graph, expands
dis[curU] = curW;
pq.push({ -curW, curU });
propTop();
} else if (curW >= getTop().first) { // you win, other should prop well, you just normal
propTop();
}
if (unex) sendTop();
}
} // namespace
void InitA (int n, int m, vi us, vi vs, vi wws) {
::n = n;
unex = n;
for (ll i = 0; i < m; i++) {
adj[us[i]].push_back({ vs[i], wws[i] });
adj[vs[i]].push_back({ us[i], wws[i] });
}
cou = 0;
curU = 0;
curW = 0;
dis = vll(n, INF);
dis[0] = 0;
pq.push({ -dis[0], 0 });
propTop();
if (unex) sendTop();
}
void ReceiveA (bool x) {
if (cou%31 < 20) curW |= x<<cou%31;
else curU |= x<<(cou%31-20);
if (cou%31 == 30) { readAll(); curW = 0; curU = 0; }
cou++;
}
vi Answer () {
return vi(dis.begin(), dis.end());
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
namespace {
const ll MAXN = 2E3+16, INF = (1<<20)-1;
int n;
int cou;
ll curU, curW;
priority_queue <pair <ll, ll> > pq;
vector <pair <ll, ll> > adj[MAXN];
bool vis[MAXN];
ll unex;
vll dis;
pair <ll, ll> getTop () {
while (pq.size() && vis[pq.top().second]) pq.pop();
if (pq.size()) return { -pq.top().first, pq.top().second };
return { INF, MAXN-4 };
}
void propTop () {
ll u = getTop().second; pq.pop();
assert(pq.size());
vis[u] = true; unex--;
for (auto [v, w] : adj[u]) {
if (dis[v] <= dis[u]+w) continue;
dis[v] = dis[u]+w;
pq.push({ -dis[v], v });
}
}
void mySend (ll x, ll bits) { for (ll i = 0; i < bits; i++) SendB(x>>i&1); }
void send (pair <ll, ll> top) {
mySend(top.first, 20);
mySend(top.second, 11);
}
void readAll () {
auto oldTop = getTop();
ll ounex = unex;
if (curW <= getTop().first) { // other wins, inserts in current graph, expands
dis[curU] = curW;
pq.push({ -curW, curU });
propTop();
} else if (curW > getTop().first) { // you win, other should prop well, you just normal
propTop();
}
if (ounex) send(oldTop);
}
} // namespace
void InitB (int n, int m, vi us, vi vs, vi wws) {
::n = n;
unex = n;
for (ll i = 0; i < m; i++) {
adj[us[i]].push_back({ vs[i], wws[i] });
adj[vs[i]].push_back({ us[i], wws[i] });
}
cou = 0;
curU = 0;
curW = 0;
dis = vll(n, INF);
dis[0] = 0;
pq.push({ -dis[0], 0 });
propTop();
// if (unex) sendTop();
}
void ReceiveB (bool x) {
if (cou%31 < 20) curW |= x<<cou%31;
else curU |= x<<(cou%31-20);
if (cou%31 == 30) { readAll(); curW = 0; curU = 0; }
cou++;
}
