#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int nx=2e3+5, inf=1e9;
int n, mn[nx], vs[nx], w, u;
vector<pair<int, int>> d[nx];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int ,int>>> pq;
vector<int> in;
pair<int, int> da, db;
void sendtop()
{
while (!pq.empty()&&vs[pq.top().second]) pq.pop();
if (pq.empty()) for (int i=0; i<29; i++) SendA(1);
else
{
auto [w, u]=pq.top();
for (int i=0; i<19; i++) SendA(w&(1<<i));
for (int i=0; i<10; i++) SendA(u&(1<<i));
}
}
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
n=N;
for (int i=1; i<N; i++) mn[i]=inf;
for (int i=0; i<A; i++) d[U[i]].push_back({V[i], C[i]}), d[V[i]].push_back({U[i], C[i]});
pq.push({0, 0});
sendtop();
}
void ReceiveA(bool x) {
in.push_back(x);
if (in.size()<29) return;
db={0, 0};
for (int i=0; i<19; i++) db.first|=(in[i]<<i);
for (int i=0; i<10; i++) db.second|=(in[19+i]<<i);
in.clear();
da=pq.empty()?make_pair(INT_MAX, INT_MAX):pq.top();
auto [w, u]=min(da, db);
if (u>=n) return;
mn[u]=w;
vs[u]=1;
for (auto [v, cw]:d[u]) if (!vs[v]&&w+cw<mn[v]) mn[v]=w+cw, pq.push({w+cw, v});
sendtop();
}
std::vector<int> Answer() {
std::vector<int> ans(n);
for (int i=0; i<n; i++) ans[i]=mn[i];
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int nx=2e3+5, inf=1e9;
int n, mn[nx], vs[nx], w, u;
vector<pair<int, int>> d[nx];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int ,int>>> pq;
vector<int> in;
pair<int, int> da, db;
void sendtop()
{
while (!pq.empty()&&vs[pq.top().second]) pq.pop();
if (pq.empty()) for (int i=0; i<29; i++) SendB(1);
else
{
auto [w, u]=pq.top();
for (int i=0; i<19; i++) SendB(w&(1<<i));
for (int i=0; i<10; i++) SendB(u&(1<<i));
}
}
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
std::vector<int> D) {
n=N;
for (int i=1; i<N; i++) mn[i]=inf;
for (int i=0; i<B; i++) d[S[i]].push_back({T[i], D[i]}), d[T[i]].push_back({S[i], D[i]});
pq.push({0, 0});
sendtop();
}
void ReceiveB(bool y) {
in.push_back(y);
if (in.size()<29) return;
da={0, 0};
for (int i=0; i<19; i++) da.first|=(in[i]<<i);
for (int i=0; i<10; i++) da.second|=(in[19+i]<<i);
in.clear();
db=pq.empty()?make_pair(INT_MAX, INT_MAX):pq.top();
auto [w, u]=min(da, db);
if (u>=n) return;
mn[u]=w;
vs[u]=1;
for (auto [v, cw]:d[u]) if (!vs[v]&&w+cw<mn[v]) mn[v]=w+cw, pq.push({w+cw, v});
sendtop();
}
