#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];
void senda(pair<int,int> x){
if(x.fi>=1e8){
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;
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);
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<<endl;
j_a=0;
d_a+=lst_a;
int cur_dis[n_a];
for (int i = 0; i < n_a; ++i) cur_dis[i]=1e9;
if(node_a<1400&&!st_a.count(node_a)) cur_dis[node_a]=d_a;
for(auto u:st_a){
vector<pair<int,int>> nabba;
for(auto i:adj_a[u]){
if(st_a.count(i.fi)) nabba.push_back(i);
}
for(auto i:nabba) adj_a[u].erase(i);
for(auto i:adj_a[u]){
cur_dis[i.fi]=min(cur_dis[i.fi],i.se+dis_a[u]);
}
}
pair<int,int> res={1e9,1e9};
for (int i = 0; i < n_a; ++i){
//cout << (cur_dis[i]==1e9 ? -2 : cur_dis[i]) <<" ";
if(cur_dis[i]==1e9) continue;
res=min(res,make_pair(cur_dis[i],i));
}//cout <<endl;
if(res.se<1e8) dis_a[res.se]=res.fi;
if(res.se<1e8) st_a.insert(res.se);
//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;
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;
void sendb(pair<int,int> x){
if(x.se>=1e8){
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++;
cnt+=2;
if(cnt==57800) return;
if(j_b==20){
//cout << "B" << " "<<node_b<<" "<<d_b<<endl;
j_b=0;
d_b+=lst_b;
lst_b=d_b;
if(node_b<1400){
st_b.insert(node_b);
dis_b[node_b]=d_b;
}
//for(auto u:st_b) cout <<u<<" ";
// cout <<endl;
int cur_dis[n_b];
for (int i = 0; i < n_b; ++i) cur_dis[i]=1e9;
for(auto u:st_b){
vector<pair<int,int>> nabba;
for(auto i:adj_b[u]){
if(st_b.count(i.fi)) nabba.push_back(i);
}
for(auto i:nabba) adj_b[u].erase(i);
for(auto i:adj_b[u]){
cur_dis[i.fi]=min(cur_dis[i.fi],i.se+dis_b[u]);
}
}
pair<int,int> res={1e9,1e9};
for (int i = 0; i < n_b; ++i){
//cout <<(cur_dis[i]==1e9 ? -1 : cur_dis[i])<<" ";
if(cur_dis[i]==1e9) continue;
if(res.fi>cur_dis[i]){
res=min(res,make_pair(cur_dis[i],i));
}
}//cout <<endl;
//cout <<res.fi-lst_b<<endl;
sendb({res.fi-lst_b,res.se});
d_b=0;
node_b=0;
}
}
