Dynamic Minimum Spanning Tree

There is a country named PS, comprising numerous cities. King Louis is determined to construct a road network that connects all the cities with the minimum total cost. Initially, some roads between cities can be built at given costs. However, due to various factors, the cost to build a road may change over time.

Whenever the cost of a road is updated, King Louis wants to immediately know the minimum total cost required to connect all the cities. In other words, after every update, you need to compute the cost of a minimum spanning tree (MST) over the cities. If it is impossible to connect all the cities, output -1.

Note: If any mathematical formulas are used, they should be written in LaTeX format. For example, the cost of the MST can be expressed as \(\min \sum_{e \in E'} w_e\) where \(E'\) is the set of edges in the MST.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of cities and the number of roads, respectively.

The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\) indicating that there is a road between city \(u\) and city \(v\) with an initial cost \(w\). Cities are numbered from 1 to \(n\).

The following line contains an integer \(q\), representing the number of update queries.

Each of the next \(q\) lines contains two integers \(index\) and \(new\_cost\), meaning that the cost for the road given by its 1-indexed order in the input is updated to \(new\_cost\).

outputFormat

For each update query, output a single line with one integer representing the minimum total cost required to connect all the cities after applying the update. If it is impossible to connect all cities, output -1.

sample

3 3
1 2 1
2 3 2
1 3 3
2
1 4
3 1

3
3