403102: GYM101005 E Roads

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.

For 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.

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.

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.

9
1 4
2 6
1 10
3 6
3 7
5 2
2 3
2 6
6
8 4 3
3 1 3
8 1 3
3 7 6
6 7 4
5 2 2

37
34
33
33
30
26