• # For Solution

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 aabbccdd 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.

Four Vertices solution codeforces

The first line contains two integers nn and mm (4n,m105)(4≤n,m≤105) — the number of vertices and edges in the graph respectively.

Each of the next mm lines contain three integers vvuuww (1v,un,vu1≤v,u≤n,v≠u1w1091≤w≤109) — 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≤q≤105) — 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≤v,u≤n,v≠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≤v,u≤n,v≠u1w1091≤w≤109). 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 aabbccdd such that there exists a path between vertices aa and bb, and there exists a path between vertices cc and dd.

Four Vertices solution codeforces

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.

Example
input

Four Vertices solution codeforces
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

output

Copy
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.