AT_asaporo_c グラフ

高桥君发现了一个连通无向图，这个图包含 $N$ 个顶点和 $M$ 条边。顶点按 $1, 2, \ldots, N$ 编号，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，且边的权值为 $c_i$。 高桥计划进行 $Q$ 次游戏。在第 $i$ 次游戏中，他选定两个顶点 $S_i$ 和 $T_i$。他需要选择一些边，使得所有顶点都可以从 $S_i$ 或 $T_i$ 出发，通过选定的那些边到达。 请你计算每次游戏中所选边的权值总和的最小可能值。

输入以下列格式提供，来自标准输入： > $N\ M\ a_1\ b_1\ c_1\ a_2\ b_2\ c_2\ \ldots\ a_M\ b_M\ c_M\ Q\ S_1\ T_1\ S_2\ T_2\ \ldots\ S_Q\ T_Q$

输出 $Q$ 行，每行表示对应游戏中边的权值总和的最小值。

- $1 \le N \le 4000$ - $1 \le M \le 400000$ - $1 \le Q \le 100000$ - $1 \le a_i, b_i, S_i, T_i \le N$ - $1 \le c_i \le 10^9$ - $a_i \neq b_i$ - $S_i \neq T_i$ - 提供的图是连通图。 ### 部分得分 - 在 $200$ 分的测试数据中，游戏次数 $Q = 1$。 - 在另外 $300$ 分的测试数据中，游戏次数 $Q \le 3000$。 ### 样例说明 1 对于每次游戏： - 第 $1$ 次游戏中，选择边 $1$ 和边 $3$，可使权值总和最小为 $8$。 - 第 $2$ 次游戏中，选择边 $1$ 和边 $2$，可使权值总和最小为 $7$。 ### 样例说明 2 这个输入同时满足两个部分得分的约束条件。 **本翻译由 AI 自动生成**