#include "Azer.h"
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 4, inf = 1e9;
#ifdef rtgsp
queue<bool> qA, qB;
void SendA (bool y)
{
qB.push(y);
}
void SendB (bool y)
{
qA.push(y);
}
#endif // rtgsp
namespace Azer
{
int u[maxn], v[maxn], w[maxn], mx = 0, cnt = 0, val = 0, sent, rem;
vector<int> adj[maxn], dist;
bool get_val = true, visited[maxn];
struct Item
{
int u, d;
bool operator < (const Item& other) const
{
return d > other.d;
}
};
priority_queue<Item> pq;
void InitA (int N, int A, vector<int> U, vector<int> V, vector<int> C)
{
dist.resize(N, inf);
dist[0] = 0;
for (int i = 0; i < A; i++)
{
u[i] = U[i]; v[i] = V[i]; w[i] = C[i];
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
}
for (int e : adj[0])
{
int vv = u[e] ^ v[e];
dist[vv] = w[e];
pq.push({vv, dist[vv]});
}
visited[0] = true;
rem = N - 1;
if (rem > 0)
{
--rem;
sent = pq.top().d;
for (int j = 0; j < 9; j++)
{
SendA((sent >> j) & 1);
}
}
}
void ReceiveA (bool x)
{
//cout << "A " << x << endl;
val = val ^ (x << cnt);
++cnt;
if (get_val == true && cnt == 9)
{
if (sent > val)
{
sent = val;
get_val = false;
}
else
{
int uu = pq.top().u;
for (int j = 0; j < 11; j++)
{
SendA((uu >> j) & 1);
}
mx += sent;
dist[uu] = mx;
visited[uu] = true;
for (int e : adj[uu])
{
int vv = u[e] ^ v[e] ^ uu;
if (dist[vv] > dist[uu] + w[e])
{
dist[vv] = dist[uu] + w[e];
pq.push({vv, dist[vv]});
}
}
if (rem > 0)
{
--rem;
while (true)
{
if (pq.empty())
{
sent = 511;
for (int j = 0; j < 9; j++)
{
SendA((sent >> j) & 1);
}
break;
}
int uu = pq.top().u, dd = pq.top().d;
if (visited[uu] == false && dist[uu] == dd)
{
sent = dd - mx;
for (int j = 0; j < 9; j++)
{
SendA((sent >> j) & 1);
}
break;
}
pq.pop();
}
}
}
cnt = val = 0;
}
else if (get_val == false && cnt == 11)
{
mx += sent;
dist[val] = mx;
visited[val] = true;
for (int e : adj[val])
{
int vv = u[e] ^ v[e] ^ val;
if (dist[vv] > dist[val] + w[e])
{
dist[vv] = dist[val] + w[e];
pq.push({vv, dist[vv]});
}
}
if (rem > 0)
{
--rem;
while (true)
{
if (pq.empty())
{
sent = 511;
for (int j = 0; j < 9; j++)
{
SendA((sent >> j) & 1);
}
break;
}
int uu = pq.top().u, dd = pq.top().d;
if (visited[uu] == false && dist[uu] == dd)
{
sent = dd - mx;
for (int j = 0; j < 9; j++)
{
SendA((sent >> j) & 1);
}
break;
}
pq.pop();
}
}
get_val = true;
cnt = val = 0;
}
}
vector<int> Answer ()
{
return dist;
}
}
#ifndef rtgsp
void InitA (int N, int A, vector<int> U, vector<int> V, vector<int> C)
{
Azer::InitA(N, A, U, V, C);
}
void ReceiveA (bool x)
{
Azer::ReceiveA(x);
}
vector<int> Answer ()
{
return Azer::Answer();
}
#endif // rtgsp
#ifdef rtgsp
int N, A, B, u, v, w;
vector<int> U, V, C, S, T, D;
//mt19937_64 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rd(0);
int main ()
{
//freopen(task".INP", "r", stdin);
//freopen(task".OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> A >> B;
for (int i = 0; i < A; i++)
{
cin >> u >> v >> w;
U.push_back(u); V.push_back(v); C.push_back(w);
}
for (int i = 0; i < B; i++)
{
cin >> u >> v >> w;
S.push_back(u); T.push_back(v); D.push_back(w);
}
Azer::InitA(N, A, U, V, C);
Baijan::InitB(N, B, S, T, D);
while (!qA.empty() || !qB.empty())
{
cout << "debug " << qA.size() << " " << qB.size() << endl;
cout << "A state : " << Azer::get_val << " " << Azer::cnt << " " << Azer::val << endl;
cout << "B state : " << Baijan::get_val << " " << Baijan::cnt << " " << Baijan::val << endl;
if (qA.empty())
{
Baijan::ReceiveB(qB.front());
qB.pop();
}
else if (qB.empty())
{
Azer::ReceiveA(qA.front());
qA.pop();
}
else
{
bool x = uniform_int_distribution<int>(0, 1)(rd);
if (x)
{
Azer::ReceiveA(qA.front());
qA.pop();
}
else
{
Baijan::ReceiveB(qB.front());
qB.pop();
}
}
}
auto d = Azer::Answer();
for (int x : d) cout << x << " ";
}
#endif // rtgsp
#include "Baijan.h"
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 4, inf = 1e9;
#ifdef rtgsp
queue<bool> qA, qB;
void SendA (bool y)
{
qB.push(y);
}
void SendB (bool y)
{
qA.push(y);
}
#endif // rtgsp
namespace Baijan
{
int u[maxn], v[maxn], w[maxn], mx = 0, cnt = 0, val = 0, sent, rem;
vector<int> adj[maxn], dist;
bool get_val = true, visited[maxn];
struct Item
{
int u, d;
bool operator < (const Item& other) const
{
return d > other.d;
}
};
priority_queue<Item> pq;
void InitB (int N, int B, vector<int> S, vector<int> T, vector<int> D)
{
dist.resize(N, inf);
dist[0] = 0;
for (int i = 0; i < B; i++)
{
u[i] = S[i]; v[i] = T[i]; w[i] = D[i];
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
}
for (int e : adj[0])
{
int vv = u[e] ^ v[e];
dist[vv] = w[e];
pq.push({vv, dist[vv]});
}
visited[0] = true;
rem = N - 1;
if (rem > 0)
{
--rem;
sent = pq.top().d;
for (int j = 0; j < 9; j++)
{
SendB((sent >> j) & 1);
}
}
}
void ReceiveB (bool x)
{
//cout << "B " << x << endl;
val = val ^ (x << cnt);
++cnt;
if (get_val == true && cnt == 9)
{
if (sent >= val)
{
sent = val;
get_val = false;
}
else
{
int uu = pq.top().u;
for (int j = 0; j < 11; j++)
{
SendB((uu >> j) & 1);
}
mx += sent;
dist[uu] = mx;
visited[uu] = true;
for (int e : adj[uu])
{
int vv = u[e] ^ v[e] ^ uu;
if (dist[vv] > dist[uu] + w[e])
{
dist[vv] = dist[uu] + w[e];
pq.push({vv, dist[vv]});
}
}
if (rem > 0)
{
--rem;
while (true)
{
if (pq.empty())
{
sent = 511;
for (int j = 0; j < 9; j++)
{
SendB((sent >> j) & 1);
}
break;
}
int uu = pq.top().u, dd = pq.top().d;
if (visited[uu] == false && dist[uu] == dd)
{
sent = dd - mx;
for (int j = 0; j < 9; j++)
{
SendB((sent >> j) & 1);
}
break;
}
pq.pop();
}
}
}
cnt = val = 0;
}
else if (get_val == false && cnt == 11)
{
mx += sent;
dist[val] = mx;
visited[val] = true;
for (int e : adj[val])
{
int vv = u[e] ^ v[e] ^ val;
if (dist[vv] > dist[val] + w[e])
{
dist[vv] = dist[val] + w[e];
pq.push({vv, dist[vv]});
}
}
if (rem > 0)
{
--rem;
while (true)
{
if (pq.empty())
{
sent = 511;
for (int j = 0; j < 9; j++)
{
SendB((sent >> j) & 1);
}
break;
}
int uu = pq.top().u, dd = pq.top().d;
if (visited[uu] == false && dist[uu] == dd)
{
sent = dd - mx;
for (int j = 0; j < 9; j++)
{
SendB((sent >> j) & 1);
}
break;
}
pq.pop();
}
}
get_val = true;
cnt = val = 0;
}
}
}
#ifndef rtgsp
void InitB (int N, int B, vector<int> S, vector<int> T, vector<int> D)
{
Baijan::InitB(N, B, S, T, D);
}
void ReceiveB (bool x)
{
Baijan::ReceiveB(x);
}
#endif // rtgsp
#ifdef rtgsp
int N, A, B, u, v, w;
vector<int> U, V, C, S, T, D;
//mt19937_64 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rd(0);
int main ()
{
//freopen(task".INP", "r", stdin);
//freopen(task".OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> A >> B;
for (int i = 0; i < A; i++)
{
cin >> u >> v >> w;
U.push_back(u); V.push_back(v); C.push_back(w);
}
for (int i = 0; i < B; i++)
{
cin >> u >> v >> w;
S.push_back(u); T.push_back(v); D.push_back(w);
}
Azer::InitA(N, A, U, V, C);
Baijan::InitB(N, B, S, T, D);
while (!qA.empty() || !qB.empty())
{
cout << "debug " << qA.size() << " " << qB.size() << endl;
cout << "A state : " << Azer::get_val << " " << Azer::cnt << " " << Azer::val << endl;
cout << "B state : " << Baijan::get_val << " " << Baijan::cnt << " " << Baijan::val << endl;
if (qA.empty())
{
Baijan::ReceiveB(qB.front());
qB.pop();
}
else if (qB.empty())
{
Azer::ReceiveA(qA.front());
qA.pop();
}
else
{
bool x = uniform_int_distribution<int>(0, 1)(rd);
if (x)
{
Azer::ReceiveA(qA.front());
qA.pop();
}
else
{
Baijan::ReceiveB(qB.front());
qB.pop();
}
}
}
auto d = Azer::Answer();
for (int x : d) cout << x << " ";
}
#endif // rtgsp
