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

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

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

输入格式

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

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

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

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

所有裁决均满足 $1 \leqslant l_j \leqslant h_j \leqslant 1\,000\,000$。

输出格式

对于每个测试用例，输出 $q$ 行，每行对应一次裁决。在第 $j$ 行中，输出满足委员会约束条件并创建最大连接城市对数量的公路网络的最小成本 $c_j$。

样例

样例输入 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)\}$。