题目描述

高桥找到了一个有 $N$ 个顶点和 $M$ 条边的无向连通图。顶点编号从 $1$ 到 $N$。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，边的权重为 $c_i$。

他将使用这个图进行 $Q$ 轮游戏。在第 $i$ 轮中，指定两个顶点 $S_i$ 和 $T_i$，然后他需要选择一部分边，使得从顶点 $S_i$ 或 $T_i$ 中的任意一个出发，可以通过选择的边到达任意一个顶点。

对于每一轮游戏，找出高桥选择的边的权重之和的最小可能值。

约束条件

• $1 ≤ N ≤ 4,000$
• $1 ≤ M ≤ 400,000$
• $1 ≤ Q ≤ 100,000$
• $1 ≤ a_i,b_i,S_i,T_i ≤ N$
• $1 ≤ c_i ≤ 10^9$
• $a_i ≠ b_i$
• $S_i ≠ T_i$
• 给定的图是连通的。

部分分数

• 在价值为 $200$ 分的测试集中，$Q = 1$。
• 在价值为另外 $300$ 分的测试集中，$Q ≤ 3000$。

输入

输入以以下格式从标准输入给出：

$N$ $M$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ : $a_M$ $b_M$ $c_M$ $Q$ $S_1$ $T_1$ $S_2$ $T_2$ : $S_Q$ $T_Q$

输出

输出 $Q$ 行，第 $i$ 行应包含高桥选择的边的权重之和的最小可能值。

示例输入 1

4 3
1 2 3
2 3 4
3 4 5
2
2 3
1 4

示例输出 1

8
7

我们来看每一轮游戏：

• 在第一轮中，选择边 $1$ 和 $3$ 的权重之和最小为 $8$。
• 在第二轮中，选择边 $1$ 和 $2$ 的权重之和最小为 $7$。

示例输入 2

4 6
1 3 5
4 1 10
2 4 6
3 2 2
3 4 5
2 1 3
1
2 3

示例输出 2

8

该输入满足两个部分分数的额外约束条件。