CF25C.Roads in Berland

There are n cities numbered from 1 to n in Berland. Some of them are connected by two-way roads. Each road has its own length — an integer number from 1 to 1000. It is known that from each city it is possible to get to any other city by existing roads. Also for each pair of cities it is known the shortest distance between them. Berland Government plans to build k new roads. For each of the planned road it is known its length, and what cities it will connect. To control the correctness of the construction of new roads, after the opening of another road Berland government wants to check the sum of the shortest distances between all pairs of cities. Help them — for a given matrix of shortest distances on the old roads and plans of all new roads, find out how the sum of the shortest distances between all pairs of cities changes after construction of each road.

伯兰德有 $n$ 座城市，编号从 $1$ 到 $n$。其中一些城市由双向道路连接。每条道路都有其自身的长度——一个介于 $1$ 到 $1000$ 之间的整数。已知从任意一座城市出发，均可通过现有道路到达其他任意一座城市。此外，对于每一对城市，均已知它们之间的最短距离。伯兰德政府计划修建 $k$ 条新道路。对于每条拟建道路，已知其长度以及它所连接的两座城市。为监控新道路建设的正确性，每次开通一条新道路后，伯兰德政府希望检查所有城市对之间最短距离的总和。请帮助他们——给定旧道路的最短距离矩阵以及所有新道路的建设计划，求出在每条新道路建成后，所有城市对之间最短距离的总和如何变化。

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.

第一行包含一个整数 $n$（$2 \leq n \leq 300$）—— Berland 国的城市数量。接下来有 $n$ 行，每行包含 $n$ 个整数 —— 最短距离矩阵。第 $i$ 行中的第 $j$ 个整数为 $d_{i,j}$，表示城市 $i$ 与城市 $j$ 之间的最短距离。保证 $d_{i,i} = 0$，$d_{i,j} = d_{j,i}$，且所给矩阵确为某组双向道路（边权为 $1$ 至 $1000$ 的整数）所对应的最短距离矩阵；并且从任意城市出发，均可通过这些道路到达其余任意城市。

下一行包含一个整数 $k$（$1 \leq k \leq 300$）—— 计划修建的道路数量。随后的 $k$ 行描述了这些计划修建的道路。每条道路由三个以空格分隔的整数 $a_i$、$b_i$、$c_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq c_i \leq 1000$）描述：$a_i$ 和 $b_i$ 表示该道路连接的两个城市，$c_i$ 表示该道路的长度。一对城市之间可能存在多条道路，但不存在连接同一城市的自环道路。

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.

输出 k 个空格分隔的整数 q__i（1 ≤ i ≤ k）。其中 q__i 应等于在修建了输入中前 i 条道路（道路按输入顺序编号，从 1 开始）之后，所有城市对之间的最短距离之和。每对城市在求和中仅计算一次，即我们统计的是无序对。