SP7025 CT25C - 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 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 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.

The first line contains integer _n_ (2 n ) — amount of cities in Berland. Then there follow _n_ lines with _n_ integer numbers each — the matrix of distances. _j_-th integer in the _i_-th row — _d_ $ _{i, j} $ , the 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 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 ) — 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} $ ) — _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 _k_ lines, each line contains one 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.