Problem Description
Potatoland has N cities, and E roads connecting those cities, and it is guaranteed that it is possible to travel between any pair of cities in Potatoland with these roads. Each road i connects cities Ai and Bi, and has a length of Li. The distance between any pair of cities is defined as the sum of lengths of the roads in the shortest path between the two cities, and the connectivity value of Potatoland is defined as the sum of distances between any two cities.
The mayor of Potatoland is planning to build a total of R new roads, in a particular order. The ith road that is built will connect cities Si and Ti with a road of length Wi. After the construction of each road, output the connectivity value of Potatoland.
Input
The first line of input will contain three integers, N, E and R.
The next E lines of input will contain three integers each, Ai, Bi and Li.
The next R lines of input will contain three integers each, Si, Ti and Wi.
Output
The output should contain R lines with one integer each, with the ith line containing the connectivity value of Potatoland after the construction of the ith road.
Limits
For all subtasks: 1 ≤ Li, Wi ≤ 109, 0 ≤ Ai, Bi, Si, Ti < N.
Subtask 1 (29%): 1 ≤ N ≤ 70, N - 1 ≤ E ≤ 2500, 1 ≤ R ≤ 100.
Subtask 2 (20%): 1 ≤ N ≤ 300, N - 1 ≤ E ≤ 45000, R = 1.
Subtask 3 (51%): 1 ≤ N ≤ 300, N - 1 ≤ E ≤ 45000, 1 ≤ R ≤ 300.
Subtask 4 (0%): Sample Testcases.
Sample Input 1
4 3 1
0 1 3
1 2 3
2 3 3
3 0 3
Sample Output 1
24
Sample Input 2
5 5 3
0 3 4
3 4 1
3 2 5
4 1 3
1 2 1
3 1 2
2 1 6
0 4 1
Sample Output 2
36
36
26