#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 *A _{i}* and

*B*, and has a length of

_{i}*L*. 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

_{i}*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 *i*th road that is built will connect cities *S _{i}* and

*T*with a road of length

_{i}*W*. After the construction of each road, output the

_{i}*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, *A _{i}*,

*B*and

_{i}*L*.

_{i}The next *R* lines of input will contain three integers each, *S _{i}*,

*T*and

_{i}*W*.

_{i}## Output

The output should contain *R* lines with one integer each, with the *i*th line containing the *connectivity value* of Potatoland after the construction of the *i*th road.

## Limits

For all subtasks: 1 ≤ L_{i}, W_{i} ≤ 10^{9}, 0 ≤ A_{i}, B_{i}, S_{i}, T_{i} < 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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 29 | 21 | 1s | 256MB | Minimum |

2 | 20 | 21 | 1s | 256MB | Minimum |

3 | 51 | 62 | 1s | 256MB | Minimum |

4 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o newroads -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512