Given 
~N~ vertices and 
~M~ weighted bidirectional edges, Bruce knows how to find the Minimal Spanning Tree (MST). But if the weight of each edge is changing, Bruce doesn't know how to efficiently find the MST after each change. Can you write a program to help Bruce?
Input Specification
The first line of input will consist of three integers, ~N~, ~M~ and 
~Q~, which are the number of vertices, number of edges, and number of weight changes.
Each of the next ~M~ lines will consist of three integers, 
~x~, 
~y~ and 
~z~ (
~1 \le x, y \le N~, 
~0 \le z \le 50\,000\,000~), which represents the bidirectional edge between ~x~ and ~y~ has the cost ~z~.
Each of the next ~Q~ lines will consist of two integers, 
~k~ and 
~d~ (
~1 \le k \le M~, 
~0 \le d \le 50\,000\,000~), which represents the 
~k-~th edge's cost changes to ~d~.
Output Specification
Output ~Q~ lines. The line ~k~ consists of 1 integer, the cost of MST after the first ~k~ changes.
Constraints
20% cases 
~N \le 1\,000~, 
~M \le 6\,000~, 
~Q \le 6\,000~.
40% cases ~N \le 1\,000~, 
~M \le 50\,000~, 
~Q \le 8\,000~.
100% cases 
~N \le 20\,000~, ~M \le 50\,000~, 
~Q \le 50\,000~.
Sample Input
5 5 3
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 6
1 1
5 3
Sample Output
14
10
9
Comments
What if graph doesn't have minimum spanning tree?
For anyone solving this problem in the future, it is guaranteed that the graph is connected.
block size 400 is more effective than either block size 500, 200, 250, 125 or 100
It does seem to vary based on the implementation
Time complexity is supposed to be
and time limit is supposed to be 2 sec.