{"raw_statement":[{"iden":"statement","content":"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.\n\nThe 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.\n\nThe first line has a single integer T, the number of test cases.\n\nEach 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.\n\n*Limits* \n\nFor 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.\n\n"},{"iden":"input","content":"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 × 104  The sum of all N, M and Q over all test cases will not exceed 3·105  1 ≤ a, b ≤ N  1 ≤ c ≤ 105 "},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the number of cities.  \n- Let $ M \\in \\mathbb{Z} $ be the number of initial rail tracks.  \n- Let $ Q \\in \\mathbb{Z} $ be the number of future tracks to be added.  \n- Let $ E_{\\text{init}} = \\{(a_i, b_i, c_i) \\mid i \\in \\{1, \\dots, M\\}\\} $ be the set of initial edges, where $ a_i, b_i \\in \\{1, \\dots, N\\} $ are endpoints and $ c_i \\in \\mathbb{R}^+ $ is the maintenance cost.  \n- Let $ E_{\\text{add}} = \\{(a_j, b_j, c_j) \\mid j \\in \\{1, \\dots, Q\\}\\} $ be the sequence of edges to be added in order.  \n\n**Constraints**  \n1. $ T \\geq 1 $  \n2. $ 1 \\leq N, M, Q \\leq 10^5 $  \n3. $ 1 \\leq a_i, b_i \\leq N $, $ c_i > 0 $ for all edges  \n\n**Objective**  \nFor each $ j \\in \\{1, \\dots, Q\\} $, after adding edge $ (a_j, b_j, c_j) $ to the graph $ G_j = (V, E_{\\text{init}} \\cup \\{(a_1, b_1, c_1), \\dots, (a_j, b_j, c_j)\\}) $, compute the minimum spanning tree (MST) cost of $ G_j $.  \nOutput the MST cost after each addition.","simple_statement":"You are given a network of N cities connected by M initial railway tracks, each with a maintenance cost. Then, Q new tracks will be added one by one. After each new track is added, find the minimum total cost to keep all cities connected (i.e., the cost of the Minimum Spanning Tree).","has_page_source":false}