2015 USP Try-outs |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

The problem statement has recently been changed. View the changes.

×
I. The Kunming-Singapore Railway

time limit per test

3 secondsmemory limit per test

128 megabytesinput

standard inputoutput

standard outputThe Kunming-Singapore Railway is a network of rail tracks (some already built, some under construction) connecting several Asian cities. The project started in 1900 with the goal to connect Kunming (China) to Singapore, through the British Empire. Afterwards, in 1918, the railway was connected to Thailand through rail track joining Bangkok and Singapore. In 2000, ASEAN (Association of Southeast Asian Nations) considered completing this railway system.

The project is scheduled for completion by 2020. Due to its importante for Southeast Asia integration, the contractors hired you to minimize the system maintenance cost. Given *N* cities that make up the Kunming-Singapore network, *M* initial rail tracks in the system and the *Q* tracks that will be built over time, you are required to compute the minimum cost do maintain the network connected after building each of these *Q* tracks. The system is initially connected if, for each pair of cities, there a set of tracks joining one to the other.

Input

The first line has a single integer *T*, the number of test cases.

Each test case spans several lines. The first line has three space-separated integers, *N*, *M*, and *Q* (described above). The next *M* lines describe the initial rail tracks, and the next *Q* lines describe the tracks to be added over time. Each track is represented as three space-separated integers, *a*, *b*, and *c*, where *a* and *b* represent the cities that are endpoints of the track, and *c* is the maintenance cost.

Limits

- 1 ≤
*T*≤ 8 - 1 ≤
*N*,*M*,*Q*≤ 3 × 10^{4} - The sum of all
*N*,*M*and*Q*over all test cases will not exceed 3·10^{5} - 1 ≤
*a*,*b*≤*N* - 1 ≤
*c*≤ 10^{5}

Output

For each test case, print *Q* lines. The *i*th line among these must have a single integer, the minimum maintenance cost after adding the *i*th track.

Example

Input

1

4 3 5

1 2 5

2 3 6

3 4 7

1 4 8

1 2 4

2 4 5

3 4 5

1 4 6

Output

18

17

15

14

14

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/20/2024 13:08:19 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|