Problem Description

Mr. Takahashi is the king of the AtCoder Kingdom. The kingdom consists of $ N $ cities numbered from $ 1 $ to $ N $ and $ M $ bidirectional roads connecting these cities. Each road has a length. For any pair of cities $ (A, B) $ in the AtCoder Kingdom, it is guaranteed that you can reach city $ B $ from city $ A $ by traversing some roads.

Mr. Takahashi believes that the happiness of the citizens of the AtCoder Kingdom greatly depends on the convenience of transportation. To investigate how happy the citizens are, he wants to calculate the total sum $ S $ of the shortest path lengths between all possible pairs of cities.

If the shortest path length between cities $ i $ and $ j $ is denoted as $ D(i,j) $, then $ S $ is expressed as:

Additionally, Mr. Takahashi plans to construct $ K $ new roads through public works. Due to this construction, there may be more than one road directly connecting the same pair of cities, but in such cases, the existing roads will not be demolished; only new roads will be added.

Your task is to write a program that constructs the new roads in the order given and calculates $ S $ each time a new road is constructed.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ : $ A_M $ $ B_M $ $ C_M $ $ K $ $ X_1 $ $ Y_1 $ $ Z_1 $ : $ X_K $ $ Y_K $ $ Z_K $

• The first line contains two integers $N\ (1\ ≦\ N\ ≦\ 400)$ and $M\ (1\ ≦M\ ≦\ 1000)$ separated by a space, representing the number of cities and roads, respectively.
• The next $ M $ lines contain information about the existing roads. The $i\ (1≦i≦M)$ line contains three integers $ A_i(1≦A_i≦N) $, $ B_i(1≦B_i≦N) $, and $ C_i(1≦C_i≦1,000) $ separated by spaces, indicating that the $ i $th road connects city $ A_i $ and $ B_i $ with a distance of $ C_i $. $ A_i≠B_i $ and there is at most one road directly connecting any pair of cities.
• It is guaranteed that for any pair of cities $ (A,B) $, you can reach city $ B $ from city $ A $ by traversing some roads.
• The $ 2+M $ line contains an integer $K\ (1≦K≦400)$, representing the number of new roads to be constructed.
• The next $ K $ lines contain information about the new roads to be constructed. The $i\ (1≦i≦K)$ line contains three integers $ X_i(1≦X_i≦N) $, $ Y_i(1≦Y_i≦N) $, and $ Z_i(1≦Z_i≦1,000) $ separated by spaces, indicating that the $ i $th new road connects city $ X_i $ and $ Y_i $ with a distance of $ Z_i $. $ X_i≠Y_i $.

Output Format

Output to the standard output in the following format:

On the $i\ (1≦i≦K)$ line, output the total sum $ S $ of the shortest path lengths between all possible pairs of cities immediately after the first $ i $ new roads have been constructed.

Ensure to end each line with a newline.

Sample Input and Output

Sample Input #1

4 3
1 2 1
2 3 1
3 4 10
2
3 4 1
1 4 1

Sample Output #1

10
8

Sample Input #2

8 16
8 7 38
2 8 142
5 2 722
8 6 779
4 6 820
1 3 316
1 7 417
8 3 41
1 4 801
3 2 126
4 2 71
8 4 738
4 3 336
7 5 717
5 6 316
2 1 501
10
6 1 950
6 1 493
1 6 308
3 4 298
2 5 518
1 5 402
4 7 625
7 6 124
3 8 166
2 4 708

Sample Output #2

13649
12878
11954
11954
11280
11058
11058
8099
8099
8099

Notes/Hints

Sample Explanation 1

The initial state is as follows: After the second construction, the graph becomes: 

见题面 Input 部分

见题面 Output 部分