codeforces#P1566G. Four Vertices

    ID: 32324 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>constructive algorithmsdata structuresgraphsgreedyimplementationshortest paths

Four Vertices

Description

You are given an undirected weighted graph, consisting of nn vertices and mm 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 aa, bb, cc, dd such that there exists a path between aa and bb, there exists a path between cc and dd, and the sum of lengths of two shortest paths from aa to bb and from cc to dd 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.

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

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

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

The next qq lines contain the queries of two types:

  • 00 vv uu — this query means deleting an edge between vv and uu (1v,un,vu)(1 \le v, u \le n, v \neq u). It is guaranteed that such edge exists in the graph.
  • 11 vv uu ww — this query means adding an edge between vertices vv and uu with weight ww (1v,un,vu1 \le v, u \le n, v \neq u, 1w1091 \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 44. It can be proven, that at each moment there exist some four vertices aa, bb, cc, dd such that there exists a path between vertices aa and bb, and there exists a path between vertices cc and dd.

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

Input

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

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

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

The next qq lines contain the queries of two types:

  • 00 vv uu — this query means deleting an edge between vv and uu (1v,un,vu)(1 \le v, u \le n, v \neq u). It is guaranteed that such edge exists in the graph.
  • 11 vv uu ww — this query means adding an edge between vertices vv and uu with weight ww (1v,un,vu1 \le v, u \le n, v \neq u, 1w1091 \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 44. It can be proven, that at each moment there exist some four vertices aa, bb, cc, dd such that there exists a path between vertices aa and bb, and there exists a path between vertices cc and dd.

Output

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

Samples

输入数据 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

Note

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

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

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

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

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