JOI 国有 $N$ 座城市，编号为 $0$ 到 $N - 1$。共有 $A$ 条铁路线，编号为 $0$ 到 $A - 1$。铁路线 $i$ ($0 \le i \le A - 1$) 连接城市 $U_i$ 和城市 $V_i$，且是双向的，票价为 $C_i$。不同的铁路线连接不同的城市对。共有 $B$ 条公交线路，编号为 $0$ 到 $B - 1$。公交线路 $j$ ($0 \le j \le B - 1$) 连接城市 $S_j$ 和城市 $T_j$，且是双向的，票价为 $D_j$。不同的公交线路连接不同的城市对，但铁路线和公交线路可能会连接同一对城市。可以通过乘坐火车和/或公交车在任意两座城市之间往返。

Azer 想知道从城市 $0$ 到每座城市的最小总票价。由于 Azer 只了解铁路线，他与只了解公交线路的 Baijan 合作。

他们通过发送和接收字符 $0$ 或 $1$ 进行交流。发送的字符总数应小于或等于 $58\,000$。

请编写程序，Azer 的程序获取铁路线信息，Baijan 的程序获取公交线路信息，通过相互通信，帮助 Azer 找出从城市 $0$ 到每座城市的最小总票价。

实现细节

你需要提交两个文件。

第一个文件名为 Azer.cpp。它代表 Azer 的行为，并应实现以下函数。该文件应包含 Azer.h。

• void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) 此函数在开始时恰好执行一次。

  • 参数 $N$ 是城市数量。
  • 参数 $A$ 是铁路线数量。
  • 参数 $U, V$ 是长度为 $A$ 的数组。$U[i]$ 和 $V[i]$ 分别是铁路线 $i$ ($0 \le i \le A - 1$) 连接的城市 $U_i$ 和 $V_i$。
  • 参数 $C$ 是长度为 $A$ 的数组。$C[i]$ 是铁路线 $i$ ($0 \le i \le A - 1$) 的票价 $C_i$。

• void ReceiveA(bool x) 此函数在每次从 Baijan 发送字符时执行。

  • 参数 $x$ 表示从 Baijan 发送的字符：true 表示字符 $1$，false 表示字符 $0$。

• std::vector<int> Answer() 此函数在所有发送的字符都被接收后恰好执行一次。此函数必须返回一个包含从城市 $0$ 到每座城市的最小总票价的数组 $Z$。

  • 返回值 $Z$ 必须是一个长度为 $N$ 的数组。如果其长度不为 $N$，你的程序将被判为 Wrong Answer [1]。$Z[k]$ ($0 \le k \le N - 1$) 必须是从城市 $0$ 到城市 $k$ 的最小总票价。特别注意，必须满足 $Z[0] = 0$。

你的程序可以在此文件中调用以下函数：

• void SendA(bool y) 使用此函数向 Baijan 发送字符。
  • 参数 $y$ 表示要发送给 Baijan 的字符：true 表示字符 $1$，false 表示字符 $0$。

第二个文件名为 Baijan.cpp。它代表 Baijan 的行为，并应实现以下函数。该文件应包含 Baijan.h。

• void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) 此函数在开始时恰好执行一次。

  • 参数 $N$ 是城市数量。
  • 参数 $B$ 是公交线路数量。
  • 参数 $S, T$ 是长度为 $B$ 的数组。$S[j]$ 和 $T[j]$ 分别是公交线路 $j$ ($0 \le j \le B - 1$) 连接的城市 $S_j$ 和 $T_j$。
  • 参数 $D$ 是长度为 $B$ 的数组。$D[j]$ 是公交线路 $j$ ($0 \le j \le B - 1$) 的票价 $D_j$。

• void ReceiveB(bool y) 此函数在每次从 Azer 发送字符时执行。

  • 参数 $y$ 表示从 Azer 发送的字符：true 表示字符 $1$，false 表示字符 $0$。

你的程序可以在此文件中调用以下函数：

• void SendB(bool x) 使用此函数向 Azer 发送字符。
  • 参数 $x$ 表示要发送给 Azer 的字符：true 表示字符 $1$，false 表示字符 $0$。

你可以假设程序执行如下：对于每个测试用例，准备了两个队列：$Q_Y$（存储 Azer 发送的字符）和 $Q_X$（存储 Baijan 发送的字符）。首先，执行 InitA 和 InitB，并将发送的字符推入相应的队列。

• 如果 $Q_X$ 或 $Q_Y$ 不为空，则从中弹出一个字符并执行相应的 ReceiveA 或 ReceiveB。但是，如果 $Q_X$ 和 $Q_Y$ 都不为空，则不确定是先执行 ReceiveA 还是 ReceiveB。
• 当在 ReceiveA 执行期间调用 SendA 时，发送的字符被推入 $Q_Y$。
• 当在 ReceiveB 执行期间调用 SendB 时，发送的字符被推入 $Q_X$。
• 如果两个队列都为空，则执行 Answer 且程序结束。

Azer 和 Baijan 发送的字符总数应小于或等于 $58\,000$。如果超过此限制，你的程序将被判为 Wrong Answer [2]。

重要提示

• 你的程序可以实现其他内部使用的函数，或使用全局变量。提交的文件将与评测程序一起编译，并成为一个单一的可执行文件。所有全局变量和内部函数都应在匿名命名空间中声明，以避免与其他文件冲突。评测时，它将作为 Azer 和 Baijan 两个进程执行。Azer 的进程和 Baijan 的进程不能共享全局变量。
• 你的程序不应使用标准输入和标准输出。你的程序不应通过任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。

编译与测试

你可以从竞赛网页下载包含示例评测程序的压缩包来测试你的程序。压缩包中还包含你的程序的示例源文件。

示例评测程序文件为 grader.cpp。为了测试你的程序，请将 grader.cpp、Azer.cpp、Baijan.cpp、Azer.h 和 Baijan.h 放在同一目录下，并运行以下命令来编译你的程序：

g++ -std=gnu++14 -O2 -o grader grader.cpp Azer.cpp Baijan.cpp

如果编译成功，将生成可执行文件 grader。

注意，实际评测程序与示例评测程序不同。示例评测程序将作为一个单一进程执行，它将从标准输入读取输入数据，并将结果写入标准输出和标准错误。

样例通信

这里是示例评测程序的输入和对应的函数调用。

样例评测程序的输入格式

示例评测程序从标准输入读取输入数据，格式如下：

N A B
U0 V0 C0
...
UA-1 VA-1 CA-1
S0 T0 D0
...
SB-1 TB-1 DB-1

样例评测程序的输出格式

示例评测程序将以下信息写入标准输出和标准错误（引号仅为清晰起见）。

• 如果你的程序被判为 Wrong Answer [1] 或 Wrong Answer [2]，它会将类型（如“Wrong Answer [1]”）写入标准错误。它不会向标准输出写入任何内容。
• 否则，它会将发送字符的总数 $L$ 以“Accepted: L”的形式写入标准错误。它还会将你的答案 $Z$ 写入标准输出，格式如下：

Z[0]
...
Z[N - 1]

示例评测程序不会检查 $Z$ 的值是否正确。

如果你的程序被判为多种类型的 Wrong Answer，示例评测程序仅报告其中一种。

数据范围

• $1 \le N \le 2\,000$
• $0 \le A \le 500\,000$
• $0 \le B \le 500\,000$
• $0 \le U_i \le N - 1$ ($0 \le i \le A - 1$)
• $0 \le V_i \le N - 1$ ($0 \le i \le A - 1$)
• $U_i \neq V_i$ ($0 \le i \le A - 1$)
• $(U_{i_1}, V_{i_1}) \neq (U_{i_2}, V_{i_2})$ 且 $(U_{i_1}, V_{i_1}) \neq (V_{i_2}, U_{i_2})$ ($0 \le i_1 < i_2 \le A - 1$)
• $0 \le S_j \le N - 1$ ($0 \le j \le B - 1$)
• $0 \le T_j \le N - 1$ ($0 \le j \le B - 1$)
• $S_j \neq T_j$ ($0 \le j \le B - 1$)
• $(S_{j_1}, T_{j_1}) \neq (S_{j_2}, T_{j_2})$ 且 $(S_{j_1}, T_{j_1}) \neq (T_{j_2}, S_{j_2})$ ($0 \le j_1 < j_2 \le B - 1$)
• 可以通过乘坐火车和/或公交车在任意两座城市之间往返。
• $1 \le C_i \le 500$ ($0 \le i \le A - 1$)
• $1 \le D_j \le 500$ ($0 \le j \le B - 1$)

子任务

1. (6 分) $A = 0$。
2. (8 分) $B \le 1\,000$。
3. (8 分) $A + B = N - 1$。
4. (38 分) $N \le 900$。
5. (14 分) $N \le 1\,100$。
6. (10 分) $N \le 1\,400$。
7. (16 分) 无附加限制。