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?
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\leq x, y \leq N~, ~0 \leq z \leq 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\leq k \leq M~, ~0 \leq d \leq 50\,000\,000~), which represents the ~k-~th edge's cost changes to ~d~.
Output ~Q~ lines. The line ~k~ consists of 1 integer, the cost of MST after the first ~k~ changes.
20% cases ~N\leq 1\,000~, ~M \leq 6\,000~, ~Q\leq 6\,000~
40% cases ~N\leq 1\,000~, ~M \leq 50\,000~, ~Q\leq 8\,000~
100% cases ~N\leq 20\,000~, ~M \leq 50\,000~, ~Q\leq 50\,000~
5 5 3 1 2 1 2 3 2 3 4 3 4 5 4 5 1 5 1 6 1 1 5 3
14 10 9