#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
namespace {
int n_a;
int lst_a=0;
int dis_a[2500];
int j_a=0;
int node_a=0;
set<int> st_a;
int d_a=0;
set<pair<int,int>> adj_a[2500];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq_a;
void senda(pair<int,int> x){
if(x.fi>=1e7){
for (int i = 0; i < 11; ++i)
{
SendA(true);
}
for (int i = 0; i < 9; ++i)
{
SendA(true);
}
}else{
int u=x.se;
int d=x.fi;
//cout <<u<<"_"<< d<<endl;
for (int i = 0; i < 11; ++i)
{
SendA((1<<i)&u);
}
for (int i = 0; i < 9; ++i)
{
SendA((1<<i)&d);
}
}
}
} // namespace
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,std::vector<int> C) {
n_a = N;
for (int i = 0; i < N; ++i)
{
dis_a[i]=1e9;
}
for (int i = 0; i < A; ++i)
{
adj_a[U[i]].insert({V[i],C[i]});
adj_a[V[i]].insert({U[i],C[i]});
}
dis_a[0]=0;
st_a.insert(0);
pq_a.push({0,0});
for(auto u:adj_a[0]) pq_a.push({u.se,u.fi});
senda({0,0});
}
void ReceiveA(bool x) {
if(0<=j_a&&j_a<11){
node_a+=(x<<j_a);
}else if(11<=j_a&&j_a<20){
d_a+=(x<<(j_a-11));
}
j_a++;
if(j_a==20){
//cout << "A" << " "<<node_a<<" "<<d_a+lst_a<<endl;
j_a=0;
d_a+=lst_a;
if(node_a<1400&&!st_a.count(node_a)) pq_a.push({d_a,node_a});
while(!pq_a.empty()&&st_a.count(pq_a.top().se)) pq_a.pop();
if(pq_a.empty()) {
senda({1e9,1e9});
node_a=0;
d_a=0;
return;
}
pair<int,int> res=pq_a.top();
//cout <<pq_a.top().fi<<endl;
pq_a.pop();
dis_a[res.se]=res.fi;
st_a.insert(res.se);
for (auto u:adj_a[res.se]) pq_a.push({res.fi+u.se,u.fi});
if(st_a.size()==n_a) return;
//for(int i=0;i<n_a;i++) cout <<(dis_a[i]==1e9 ? -1 :dis_a[i])<<" ";
// cout <<endl;
//cout <<res.fi-lst_a<<endl;
//cout <<res.fi-lst_a<<" "<<res.se<<endl;
senda({res.fi-lst_a,res.se});
lst_a=res.fi;
node_a=0;
d_a=0;
}
}
std::vector<int> Answer() {
std::vector<int> ans(n_a);
for (int k = 0; k < n_a; ++k) {
ans[k] = dis_a[k];
}
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
namespace {
int n_b;
int j_b=0;
int cnt=0;
int lst_b=0;
int node_b=0;
int d_b=0;
set<pair<int,int>> adj_b[2500];
int dis_b[2500];
set<int> st_b;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq_b;
void sendb(pair<int,int> x){
if(x.se>=1e7){
for (int i = 0; i < 11; ++i)
{
SendB(true);
}
for (int i = 0; i < 9; ++i)
{
SendB(true);
}
}else{
int u=x.se;
int d=x.fi;
for (int i = 0; i < 11; ++i)
{
SendB((1<<i)&u);
}
for (int i = 0; i < 9; ++i)
{
SendB((1<<i)&d);
}
}
}
} // namespace
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,std::vector<int> D) {
n_b=N;
for (int i = 0; i < B; ++i)
{
adj_b[S[i]].insert({T[i],D[i]});
adj_b[T[i]].insert({S[i],D[i]});
}
for (int i = 0; i < N; ++i)
{
dis_b[i]=1e9;
}
}
void ReceiveB(bool y) {
if(0<=j_b&&j_b<11){
node_b+=(y<<j_b);
}else if(11<=j_b&&j_b<20){
d_b+=(y<<(j_b-11));
}
j_b++;
if(j_b==20){
//cout << "B" << " "<<node_b<<" "<<d_b<<endl;
j_b=0;
if(node_b<1400&&!st_b.count(node_b)){
d_b+=lst_b;
lst_b=d_b;
for (auto u:adj_b[node_b]) pq_b.push({d_b+u.se,u.fi});
st_b.insert(node_b);
dis_b[node_b]=d_b;
}
//for(auto u:st_b) cout <<u<<" ";
// cout <<endl;
while(!pq_b.empty()&&st_b.count(pq_b.top().se)) pq_b.pop();
if(pq_b.empty()){
sendb({1e9,1e9});
d_b=0;
node_b=0;
return;
}
pair<int,int> res=pq_b.top();
//cout <<res.fi-lst_b<<endl;
sendb({res.fi-lst_b,res.se});
d_b=0;
node_b=0;
}
}
