CF1566G.Four Vertices

You are given an undirected weighted graph, consisting of $n$ vertices and $m$ edges.

Some queries happen with this graph:

• Delete an existing edge from the graph.
• Add a non-existing edge to the graph.

At the beginning and after each query, you should find four different vertices $a$, $b$, $c$, $d$ such that there exists a path between $a$ and $b$, there exists a path between $c$ and $d$, and the sum of lengths of two shortest paths from $a$ to $b$ and from $c$ to $d$ is minimal. The answer to the query is the sum of the lengths of these two shortest paths. The length of the path is equal to the sum of weights of edges in this path.

给你一个包含 $n$ 个顶点和 $m$ 条边的无向带权图。

该图上会进行若干次查询，每次查询为以下两种操作之一：

• 从图中删除一条已存在的边；
• 向图中添加一条不存在的边。

在初始状态以及每次查询之后，你都需要找出四个互不相同的顶点 $a$、$b$、$c$、$d$，使得：

• $a$ 与 $b$ 之间存在路径，
• $c$ 与 $d$ 之间存在路径，
• 且从 $a$ 到 $b$ 的最短路径长度与从 $c$ 到 $d$ 的最短路径长度之和最小。

该查询的答案即为这两个最短路径长度之和。路径的长度定义为该路径上所有边的权重之和。

The first line contains two integers $n$ and $m$ $(4 \le n, m \le 10^5)$ — the number of vertices and edges in the graph respectively.

Each of the next $m$ lines contain three integers $v$, $u$, $w$ ($1 \le v, u \le n, v \neq u$, $1 \le w \le 10^9$) — this triple means that there is an edge between vertices $v$ and $u$ with weight $w$.

The next line contains a single integer $q$ $(0 \le q \le 10^5)$ — the number of queries.

The next $q$ lines contain the queries of two types:

• $0$ $v$ $u$ — this query means deleting an edge between $v$ and $u$ $(1 \le v, u \le n, v \neq u)$. It is guaranteed that such edge exists in the graph.
• $1$ $v$ $u$ $w$ — this query means adding an edge between vertices $v$ and $u$ with weight $w$ ($1 \le v, u \le n, v \neq u$, $1 \le w \le 10^9$). It is guaranteed that there was no such edge in the graph.

It is guaranteed that the initial graph does not contain multiple edges.

At the beginning and after each query, the graph doesn't need to be connected.

It is guaranteed that at each moment the number of edges will be at least $4$. It can be proven, that at each moment there exist some four vertices $a$, $b$, $c$, $d$ such that there exists a path between vertices $a$ and $b$, and there exists a path between vertices $c$ and $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$ 之间也存在路径。

Print $q + 1$ integers — the minimal sum of lengths of shortest paths between chosen pairs of vertices before the queries and after each of them.

输出 $q + 1$ 个整数——即在所有查询之前，以及每次查询之后，所选顶点对之间最短路径长度之和的最小值。

Before the queries you can choose vertices $(a, b) = (3, 2)$ and $(c, d) = (1, 4)$. The sum of lengths of two shortest paths is $3 + 1 = 4$.

After the first query you can choose vertices $(a, b) = (2, 5)$ and $(c, d) = (1, 4)$. The sum of lengths of two shortest paths is $2 + 1 = 3$.

After the second query you can choose vertices $(a, b) = (3, 4)$ and $(c, d) = (2, 5)$. The sum of lengths of two shortest paths is $1 + 2 = 3$.

After the third query, you can choose vertices $(a, b) = (2, 6)$ and $(c, d) = (4, 5)$. The sum of lengths of two shortest paths is $4 + 3 = 7$.

After the last query you can choose vertices $(a, b) = (1, 6)$ and $(c, d) = (2, 5)$. The sum of lengths of two shortest paths is $3 + 2 = 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$。