403153: GYM101047 I The Kunming-Singapore Railway

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 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⁴
• The sum of all N, M and Q over all test cases will not exceed 3·10⁵
• 1 ≤ a, b ≤ N
• 1 ≤ c ≤ 10⁵

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

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

18
17
15
14
14