题目描述

Misha 成功解决了选拔阶段的所有题目，因此获得了参加闭门奥林匹克信息学决赛的邀请。Misha 打算乘飞机前往比赛地点，并且他希望最多换乘一次，也就是说最多使用两个航班。在所有这样的方案中，他当然关心最便宜的一个。

闭门奥林匹克的评委会严格保密决赛的地点和日期，而 Misha 又非常喜欢旅行，所以他无法提前知道自己会从哪个城市出发。此外，新的定期航班会不时出现，一些旧航班也会从时刻表中消失。因此，Misha 请你编写一个程序，支持以下请求：

1. 添加一个新的定期航班。
2. 删除某个航班。
3. 在只考虑直达路线和恰好一次换乘路线的情况下，求两个城市之间的最低费用。

每个航班连接一对城市 $u_i$ 和 $v_i$，并有费用 $c_i$。所有航班都是双向的，也就是说可以从 $u_i$ 到 $v_i$，也可以从 $v_i$ 到 $u_i$。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示城市数量和当前已有航班数量。

$$2 \le n \le 100000,\quad 0 \le m \le 100000$$

接下来 $m$ 行描述已有航班。第 $i$ 行包含三个整数 $u_i,v_i,c_i$，表示第 $i$ 个定期航班连接的两个城市以及费用。

$$1 \le u_i,v_i \le n,\quad u_i \ne v_i,\quad 0 \le c_i \le 10^9$$

下一行包含一个整数 $q$，表示请求数量。

$$1 \le q \le 100000$$

接下来 $q$ 行，每行按以下三种格式之一描述一个请求：

• 1 ui vi ci：添加一条城市 $u_i$ 和 $v_i$ 之间、费用为 $c_i$ 的定期航班。

  $$1 \le u_i,v_i \le n,\quad u_i \ne v_i,\quad 0 \le c_i \le 10^9$$

• 2 ui vi：取消城市 $u_i$ 和 $v_i$ 之间的定期航班。

  $$1 \le u_i,v_i \le n,\quad u_i \ne v_i$$

  保证在收到该请求时，城市 $u_i$ 和 $v_i$ 之间确实有定期航班。

• 3 ui vi：询问 Misha 从城市 $u_i$ 到城市 $v_i$，在最多一次换乘的限制下，最低费用是多少。

  $$1 \le u_i,v_i \le n,\quad u_i \ne v_i$$

保证任意时刻每一对城市之间最多存在一条定期航班。额外保证，输入中至少存在一个第三类请求。

输出格式

对于每个第三类请求，输出使用不超过一次换乘从指定城市出发到达指定城市的最小费用。

如果两座城市之间不存在满足条件的路线，输出 $-1$。

样例

输入

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

输出

7
9
10
1
-1
1
4
14
-1

样例解释

对于样例中的第三类请求，按出现顺序列出最优路线：

1. 经过城市 $2$。虽然存在直达航班，但它不是最便宜的路线。
2. 经过城市 $3$。
3. 经过城市 $2$。
4. 经过城市 $3$。
5. 不存在满足条件的路线。
6. 直达航班。
7. 经过城市 $1$。
8. 经过城市 $4$。
9. 不存在满足条件的路线。

评分方式

本题共有若干组测试。每组分数只有在通过该组所有测试以及所有前置测试组后才会获得。Offline 检查表示该组测试结果只会在比赛结束后公布。

组别	分数	附加限制	说明
0		-	样例测试
1	20	$n,m,q \le 100$	-
2		$n,m,q \le 3000$
3		任意时刻从每个城市出发的航班数不超过 $500$
4	40	-	Offline 检查