The Kunming-Singapore Railway
By Arthur Nascimento, Universidade de São Paulo 
Brazil
By Arthur Nascimento, Universidade de São Paulo Brazil
The 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.
The input is composed of many instances. The first line of the input contains an integer T which indicates the number of instances.
Each instance spans several lines. The first line has three space-separated integers, N, M, and Q (described above, 1 ≤ N, M, Q ≤ 3*104). 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 (1 ≤ a, b ≤ N e 1 ≤ c ≤ 3*104), where a and b represent the cities that are endpoints of the track, and c is the maintenance cost.
For each instance, print Q lines. The i-th line among these must have a single integer, the minimum maintenance cost after adding the i-th track.
| Input Sample | Output Sample |
|
1 |
18 |