给你一个无向加权图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。
此图发生一些查询:
- 从图表中删除现有边。
- 向图中添加一条不存在的边。
在每个查询的开始和之后,您应该找到四个不同的顶点 $$$a$$$、$$$b$$$、$$$c$$$、$$$d$$$,使得 $$$a$$$ 和 $$$b$$$ 之间存在路径,$$$c$$$ 和 $$$d$$$ 之间存在路径,以及从$$$a$$$ 到 $$$b$$$ 以及从 $$$c$$$ 到 $$$d$$$ 是最小的。查询的答案是这两条最短路径的长度之和。路径的长度等于该路径中边的权重之和。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(4 \le n, m \le 10^5)$$$ - 分别是图中的顶点数和边数。
接下来的 $$$m$$$ 行包含三个整数 $$$v$$$, $$$u$$$, $$$w$$$ ($$$1 \le v, u \le n, v \neq u$$$, $$$1 \le w \le 10^9$$$) - 这个三元组意味着顶点 $$$v$$$ 和$$$u$$$ 重量为 $$$w$$$。
下一行包含一个整数 $$$q$$$ $$$(0 \le q \le 10^5)$$$ — 查询数。
接下来的 $$$q$$$ 行包含两种类型的查询:
- $$$0$$$ $$$v$$$ $$$u$$$ - 此查询意味着删除 $$$v$$$ 和 $$$u$$$ $$$(1 \le v, u \le n, v \neq u)$$$ 之间的边。保证图中存在这样的边。
- $$$1$$$ $$$v$$$ $$$u$$$ $$$w$$$ - 此查询意味着在顶点 $$$v$$$ 和 $$$u$$$ 之间添加一条边,权重为 $$$w$$$ ($$$1 \le v, u \le n, v \neq u$$$, $$$1 \le w \le 10^9$$$)。保证图中不存在这样的边。
保证初始图不包含多条边。
在每次查询开始时和之后,不需要连接图。
保证每一时刻的边数至少为$$$4$$$。可以证明,每一时刻都存在四个顶点$$$a$$$、$$$b$$$、$$$c$$$、$$$d$$$,使得顶点$$$a$$$和$$$b$$$之间存在路径,顶点$$$c$$$和$$$d$$$之间存在路径。
输出
打印 $$$q + 1$$$ 整数 - 查询之前和每个查询之后所选顶点对之间最短路径长度的最小总和。
示例
输入 #1
6 6 1 3 6 4 3 1 1 4 1 2 6 4 2 4 2 5 4 3 4 1 2 5 2 0 1 4 0 3 4 1 6 1 3
输出 #1
4 3 3 7 5
注意
在查询之前,您可以选择顶点 $$$(a, b) = (3, 2)$$$ 和 $$$(c, d) = (1, 4)$$$。两条最短路径的长度之和为$$$3 + 1 = 4$$$。
第一次查询后,您可以选择顶点 $$$(a, b) = (2, 5)$$$ 和 $$$(c, d) = (1, 4)$$$。两条最短路径的长度之和为$$$2 + 1 = 3$$$。
第二次查询后,您可以选择顶点 $$$(a, b) = (3, 4)$$$ 和 $$$(c, d) = (2, 5)$$$。两条最短路径的长度之和为$$$1 + 2 = 3$$$。
第三次查询后,您可以选择顶点 $$$(a, b) = (2, 6)$$$ 和 $$$(c, d) = (4, 5)$$$。两条最短路径的长度之和为$$$4 + 3 = 7$$$。
最后一次查询后,您可以选择顶点 $$$(a, b) = (1, 6)$$$ 和 $$$(c, d) = (2, 5)$$$。两条最短路径的长度之和为$$$3 + 2 = 5$$$。