CT25C  Roads in Berland
There are n cities numbered from 1 to n in Berland. Some of them are connected by twoway 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.
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 distances. jth integer in the ith 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 twoway 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 spaceseparated 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 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.
Example
Input:3
0 4 5
4 0 9
5 9 0
2
2 3 8
1 2 1
Output:
17
12
hide comments
Augusto:
20160320 15:28:39
I got confused with the statement when it says "Also for each pair of cities it is known the distance between them". I don't know what it means with "the distance", I think it means "some distance" or something but it is NOT the shortest distance. Last edit: 20160320 15:35:23 

Bhavik:
20140223 15:00:39
nice question...:))WFI algo works here Last edit: 20140223 15:05:10 

ymGXX:
20101210 06:51:07
SPFA AC in 2.14s with constantoptimization 

pankaj:
20101022 08:09:20
sometime strange things happens. My AC solution gave TLE on second time submission. !!! Last edit: 20101022 08:09:31 

LeppyR64:
20100807 21:33:38
After each of the k roads is built does it continue to exist for the rest of the k roads?


Mohamed Maher:
20100807 13:11:00
is there any explaination for the test cases 

Krunal Manik:
20100807 09:40:46
@Phan Công Minh


Phan Công Minh:
20100807 09:40:46
Acc on codeforces doesn't mean you'll get acc here. There's some different conditions between codeforces and Spoj.


Mohamed Maher:
20100807 09:40:46
i think there is somthing wrong in test data i'm sure becz


Islam Diaa:
20100807 09:40:46
Please check the test data..I got Accepted on CodeForces and still getting WA here. 
Added by:  Phan Công Minh 
Date:  20100806 
Time limit:  0.126s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 VB.NET 
Resource:  Based on codeforces 