#include "Azer.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <iostream>
#define fs first
#define se second
using namespace std;
typedef pair<int, int> pii;
namespace {
const int inf = 1e9;
const int non = 505;
int n;
vector<pii> edge[2000];
int dist[2000];
queue<int> r;
priority_queue<pii> q;
int mode, mx, nd, nx;
int sync[2000];
} // namespace
static int get(int bit) {
int ret = 0;
for (int i = 0; i < bit; ++i) {
if (r.front()) ret |= 1 << i;
r.pop();
}
return ret;
}
static void send(int x, int bit) {
while (bit--) {
SendA(x & 1);
x >>= 1;
}
}
static void sendNext() {
nd = non + mx;
while (!q.empty()) {
int d, x;
tie(d, x) = q.top();
d = -d;
if (dist[x] != d) {
q.pop();
continue;
}
if (sync[x]) {
q.pop();
for (pii i : edge[x]) {
if (sync[i.fs]) continue;
if (dist[i.fs] <= dist[x] + i.se) continue;
dist[i.fs] = dist[x] + i.se;
q.emplace(-dist[i.fs], i.fs);
}
continue;
}
nd = d;
nx = x;
break;
}
nd -= mx;
send(nd, 9);
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
n = N;
for (int i = 0; i < A; ++i) {
edge[U[i]].emplace_back(V[i], C[i]);
edge[V[i]].emplace_back(U[i], C[i]);
}
for (int i = 1; i < n; ++i) dist[i] = inf;
q.emplace(0, 0);
sync[0] = 1;
sendNext();
}
static void pro1() {
int bd = get(9);
if (nd == non && bd == non) return;
if (nd < bd) {
sync[nx] = 1;
mx = dist[nx];
send(nx, 11);
sendNext();
}
else {
mode = 1;
mx += bd;
}
}
static void pro2() {
int bx = get(11);
dist[bx] = mx;
sync[bx] = 1;
q.emplace(-dist[bx], bx);
sendNext();
mode = 0;
}
void ReceiveA(bool x) {
r.push(x);
if (mode == 0 && r.size() == 9) pro1();
else if (mode == 1 && r.size() == 11) pro2();
}
vector<int> Answer() {
vector<int> ans;
for (int i = 0; i < n; ++i) ans.push_back(dist[i]);
return ans;
}
#include "Baijan.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <iostream>
#define fs first
#define se second
using namespace std;
typedef pair<int, int> pii;
namespace {
const int inf = 1e9;
const int non = 505;
int n;
vector<pii> edge[2000];
int dist[2000];
queue<int> r;
priority_queue<pii> q;
int mode, mx, nd, nx;
int sync[2000];
} // namespace
static int get(int bit) {
int ret = 0;
for (int i = 0; i < bit; ++i) {
if (r.front()) ret |= 1 << i;
r.pop();
}
return ret;
}
static void send(int x, int bit) {
while (bit--) {
SendB(x & 1);
x >>= 1;
}
}
static void sendNext() {
nd = non + mx;
while (!q.empty()) {
int d, x;
tie(d, x) = q.top();
d = -d;
if (dist[x] != d) {
q.pop();
continue;
}
if (sync[x]) {
q.pop();
for (pii i : edge[x]) {
if (sync[i.fs]) continue;
if (dist[i.fs] <= dist[x] + i.se) continue;
dist[i.fs] = dist[x] + i.se;
q.emplace(-dist[i.fs], i.fs);
}
continue;
}
nd = d;
nx = x;
break;
}
nd -= mx;
send(nd, 9);
}
void InitB(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
n = N;
for (int i = 0; i < A; ++i) {
edge[U[i]].emplace_back(V[i], C[i]);
edge[V[i]].emplace_back(U[i], C[i]);
}
for (int i = 1; i < n; ++i) dist[i] = inf;
q.emplace(0, 0);
sync[0] = 1;
sendNext();
}
static void pro1() {
int bd = get(9);
if (nd == non && bd == non) return;
if (nd <= bd) {
sync[nx] = 1;
mx = dist[nx];
send(nx, 11);
sendNext();
}
else {
mode = 1;
mx += bd;
}
}
static void pro2() {
int bx = get(11);
dist[bx] = mx;
sync[bx] = 1;
q.emplace(-dist[bx], bx);
sendNext();
mode = 0;
}
void ReceiveB(bool x) {
r.push(x);
if (mode == 0 && r.size() == 9) pro1();
else if (mode == 1 && r.size() == 11) pro2();
}
