#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int nx=2e3+5, inf=1e9, mx=1e6+5;
int n, mn[nx], vs[nx], w, u, cnt, exp, sz[mx], qry;
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()
{
if (cnt>n) return;
qry+=sz[cnt]+11;
if (qry>29000)
{
while (1)
{
}
}
while (!pq.empty()&&vs[pq.top().second]) pq.pop();
if (pq.empty()) for (int i=0; i<sz[cnt]+11; i++) SendA(1);
else
{
auto [w, u]=pq.top();
for (int i=0; i<sz[cnt]; i++) SendA(w&(1<<i));
for (int i=0; i<11; 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});
cnt=1;
for (int i=1; i<=n; i++) sz[i]=ceil(log2(500*i));
sendtop();
}
void ReceiveA(bool x) {
in.push_back(x);
if (in.size()<11+sz[cnt]) return;
db={0, 0};
for (int i=0; i<sz[cnt]; i++) db.first|=(in[i]<<i);
for (int i=0; i<11; i++) db.second|=(in[sz[cnt]+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});
cnt++;
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, mx=1e6+5;
int n, mn[nx], vs[nx], w, u, cnt, exp, sz[mx];
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()
{
if (cnt>n) return;
while (!pq.empty()&&vs[pq.top().second]) pq.pop();
if (pq.empty()) for (int i=0; i<sz[cnt]+11; i++) SendB(1);
else
{
auto [w, u]=pq.top();
for (int i=0; i<sz[cnt]; i++) SendB(w&(1<<i));
for (int i=0; i<11; 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});
cnt=1;
for (int i=1; i<=n; i++) sz[i]=ceil(log2(500*i));
sendtop();
}
void ReceiveB(bool y) {
in.push_back(y);
//cout<<"debug "<<sz[cnt]<<' '<<cnt<<'\n';
if (cnt>n||in.size()<11+sz[cnt]) return;
da={0, 0};
for (int i=0; i<sz[cnt]; i++) da.first|=(in[i]<<i);
for (int i=0; i<11; i++) da.second|=(in[sz[cnt]+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});
cnt++;
sendtop();
}
