赢得选举比你预想的要简单：你只需要承诺最终建立一套高质量、全国性的公路基础设施，当然，前提是不能让预算崩溃……然而，你的快乐并没有持续太久：似乎市民们已经找到了一种方法来让你真正兑现你的承诺！

你的国家有 $n$ 个主要城市。交通部准备了一份详细的地图，列出了 $m$ 条可能的公路连接及其建设成本。质量保证委员会不允许你建造单价低于 $l$ 的公路，而国家支出监管委员会不允许你建造单价高于 $h$ 的公路。为了宣称拥有“全国性”网络，你必须在上述两个限制条件下，尽可能多地连接城市对（可以间接连接）。你必须找到实现这一目标的最廉价方案，而且必须快速找到它！在所有满足限制条件且连接城市对数量最多的网络中，计算出最廉价方案的成本。

更糟糕的是，两个委员会都受到你愤怒的竞争对手的严重影响：每次你发布精心准备的计划时，他们都会立即更改 $l$ 和 $h$ 的规定，你不得不从头开始。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述：

每个测试用例的第一行包含整数 $n$ 和 $m$ ($1 \le n \le 1000; 0 \le m \le 100\,000$)，分别表示国家中的城市数量和可能的直接连接数量。

接下来的 $m$ 行，每行包含三个整数 $x, y, w$ ($1 \le x \neq y \le n; 1 \le w \le 1\,000\,000$)，表示城市 $x$ 和 $y$ 之间可以通过成本为 $w$ 的双向公路连接。连接同一对城市可能有多种方式。

接下来的一行包含一个整数 $q$ ($1 \le q \le 1\,000\,000$)，表示委员会的规定次数。

接下来的 $q$ 行，每行包含两个整数。第一行包含直接给出的初始规定 $l_1, h_1$。其余规定是加密的。对于 $j > 1$，第 $j$ 行的数字为 $l_j + c_{j-1}$ 和 $h_j + c_{j-1}$，其中 $l_j$ 和 $h_j$ 是实际的规定，$c_{j-1}$ 是前一次规定 $l_{j-1}$ 和 $h_{j-1}$ 的正确答案。

所有规定满足 $1 \le l_j \le h_j \le 1\,000\,000$。

输出格式

对于每个测试用例，输出 $q$ 行，每行对应一次规定。在第 $j$ 行中，输出满足委员会限制条件并创造最大连接城市对数量的公路网络的最少成本 $c_j$。

数据范围

输入文件大小不超过 $24.0$ MiB。

样例

样例输入 1

1
5 7
1 2 2
2 3 4
3 4 3
4 5 1
5 1 3
2 5 4
1 4 5
5
1 2
4 7
11 12
11 13
18 19

样例输出 1

3
9
8
14
13

说明

委员会的实际规定为： $(1, 2), (1, 4), (2, 3), (3, 5)$ 和 $(4, 5)$。

满足这些规定的最廉价公路网络分别由以下连接组成： $\{(1, 2), (4, 5)\}, \{(2, 1), (1, 5), (5, 4), (4, 3)\}, \{(1, 2), (1, 5), (3, 4)\}, \{(1, 5), (5, 2), (2, 3), (3, 4)\}$ 和 $\{(3, 2), (2, 5), (1, 4)\}$。