{"raw_statement":[{"iden":"statement","content":"The minister of transport of Byteland decided he needs to increase his popularity in order to aspire for presidency. Therefore, he wants to create a program that will maintain a system of transport vital to the country.\n\nFor now he is interested in the most important N cities and he wants the system of transport to contain N - 1 roads in such a way that each city is connected to the capital (the city labeled with 1) and the total maintenance cost of the streets is as small as possible. Even though he found the optimal solution, in the future, M new roads will be built between the N cities so sometimes it might be better to modify the system of transport in order to have a minimum cost.\n\nThe first line of the input contains a single integer N. Each of the next N - 1 lines contains information about the initial system of transport. On line i there are two integers K and C, representing the city closest to capital that is connected to city i and the cost of maintenance of the street connecting these two cities. If the city is directly connected to the capital then K = 1.\n\nLine N + 1 contains an integer M. Each of the next M lines contains 3 integers X, Y and C, representing the fact that a new road is build between cities X and Y, having a maintenance cost equal to C.\n\nThe output should contain M lines. On line i print a single integer representing the minimum cost of the system of transportation after the first i roads have been built.\n\n"},{"iden":"input","content":"The first line of the input contains a single integer N. Each of the next N - 1 lines contains information about the initial system of transport. On line i there are two integers K and C, representing the city closest to capital that is connected to city i and the cost of maintenance of the street connecting these two cities. If the city is directly connected to the capital then K = 1.Line N + 1 contains an integer M. Each of the next M lines contains 3 integers X, Y and C, representing the fact that a new road is build between cities X and Y, having a maintenance cost equal to C."},{"iden":"output","content":"The output should contain M lines. On line i print a single integer representing the minimum cost of the system of transportation after the first i roads have been built."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of cities, with city $ 1 $ as the capital.  \nLet $ T = (V, E_{\\text{init}}) $ be the initial tree with $ V = \\{1, 2, \\dots, N\\} $ and $ |E_{\\text{init}}| = N-1 $, where each edge $ (k, i) \\in E_{\\text{init}} $ (for $ i = 2, \\dots, N $) connects city $ i $ to its parent $ k $ (with $ k=1 $ if directly connected to the capital) and has weight $ C $.  \n\nLet $ M \\in \\mathbb{Z}^+ $ be the number of new roads.  \nLet $ R = \\{(x_j, y_j, c_j) \\mid j \\in \\{1, \\dots, M\\}\\} $ be the sequence of new edges, each with endpoints $ x_j, y_j \\in V $ and weight $ c_j \\in \\mathbb{R}^+ $.\n\n**Constraints**  \n1. $ 2 \\le N \\le 10^5 $  \n2. $ 1 \\le M \\le 10^5 $  \n3. For each initial edge $ (k, i, C) $: $ 1 \\le k < i \\le N $, $ 1 \\le C \\le 10^9 $  \n4. For each new edge $ (x_j, y_j, c_j) $: $ 1 \\le x_j, y_j \\le N $, $ x_j \\ne y_j $, $ 1 \\le c_j \\le 10^9 $\n\n**Objective**  \nAfter each new road $ j \\in \\{1, \\dots, M\\} $ is added to the graph, let $ G_j = (V, E_{\\text{init}} \\cup \\{(x_1, y_1, c_1), \\dots, (x_j, y_j, c_j)\\}) $.  \nCompute the minimum spanning tree (MST) cost of $ G_j $, and output it on line $ j $.","simple_statement":"You are given N cities, with city 1 as the capital. Initially, there are N-1 roads forming a tree connecting all cities to the capital. Each road has a maintenance cost.\n\nThen, M new roads will be added one by one. After each new road is added, you must output the minimum total cost to keep all cities connected to the capital, using any subset of the roads built so far (including the original ones and the new ones).\n\nIn short:  \nStart with a tree. Add M edges one by one. After each addition, find the minimum spanning tree cost of the current graph (still connecting all cities to the capital).","has_page_source":false}