Bitcity 是 Byteland 的首都。

Bitcity 有一个现代化的公路系统，并且该系统经常更新——会有更多的公路被添加到系统中。该系统由连接各个交叉路口的公路组成。

你作为运输公司的经理，打算将计算机从一个交叉路口运输到另一个交叉路口。但在 Byteland，燃料成本非常昂贵，因此你希望只使用一辆卡车进行运输。

你希望尽可能多地运输计算机，但所有的公路都有一个限制 $W$，这意味着载有超过 $W$ 台计算机的卡车无法通过该公路。

你必须计算出你可以运输的计算机的最大数量。

题目保证在初始公路系统中，你可以从任何一个交叉路口到达其他任何一个交叉路口。换句话说，原始系统是连通的。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 3$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $N$ 和 $M$，分别表示交叉路口和公路的数量 ($3 \le N \le 70000, N - 1 \le M \le 150000$)。

接下来的 $M$ 行，每行包含三个整数 $a, b, c$，表示在 $a$ 和 $b$ 之间有一条公路，且该公路的限制为 $c$ ($1 \le a, b \le N, 1 \le c \le 10000$)。

下一行包含一个整数 $Q$ ($1 \le Q \le 105000$)，表示查询的数量。

所有的查询属于以下两种形式之一：

1. 1 a b c：在 $a$ 和 $b$ 之间添加一条新的公路，限制为 $c$。
2. 2 a b：计算从 $a$ 到 $b$ 可以运输的计算机的最大数量 ($1 \le a, b \le N, 1 \le c \le 10000$)。

两个交叉路口之间可能存在两条或多条公路。

输出格式

对于每个第二类查询，输出可以运输的计算机的最大数量。

样例

样例输入 1

1
5 6
1 2 2
1 3 3
2 4 7
2 5 1
3 4 6
3 5 5
4
2 2 5
1 4 5 8
2 2 5
2 3 4

样例输出 1

5
7
6