Roads in Berland

Description:

Input:

The first line contains integer n (2 ≤ n ≤ 300) — amount of cities in Berland. Then there follow n lines with n integer numbers each — the matrix of shortest distances. j-th integer in the i-th row — d_i, j, the shortest distance between cities i and j. It is guaranteed that d_i, i = 0, d_i, j = d_j, i, and a given matrix is a matrix of shortest distances for some set of two-way roads with integer lengths from 1 to 1000, such that from each city it is possible to get to any other city using these roads.

Next line contains integer k (1 ≤ k ≤ 300) — amount of planned roads. Following k lines contain the description of the planned roads. Each road is described by three space-separated integers a_i, b_i, c_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 1 ≤ c_i ≤ 1000) — a_i and b_i — pair of cities, which the road connects, c_i — the length of the road. It can be several roads between a pair of cities, but no road connects the city with itself.

Output:

Output k space-separated integers q_i (1 ≤ i ≤ k). q_i should be equal to the sum of shortest distances between all pairs of cities after the construction of roads with indexes from 1 to i. Roads are numbered from 1 in the input order. Each pair of cities should be taken into account in the sum exactly once, i. e. we count unordered pairs.

Sample Input:

2
0 5
5 0
1
1 2 3

Sample Output:

3 

Sample Input:

3
0 4 5
4 0 9
5 9 0
2
2 3 8
1 2 1

Sample Output:

17 12