問題文
高桥先生是Atcoder王国的国王。他统治的Atcoder王国, 编号至1 如果要将其更改为输出最多为 N 编号最多为 N 具有双向访问连接的城市 M 由一条主干道组成。每条路都有长度。 Atcoder 王国中城市的任意组合 关于 (A,B) , 沿着A 的一些道路行驶 保证您可以达到 B 。
高桥先生认为,Atcoder人民的幸福很大程度上取决于交通的便利程度。 为了了解人们的幸福程度,我们计算了所有可能城市之间的最短路线长度的总和。 我想找到 S 。
都市 i 和 将其放在 j 之间的最短路径长度是 D(i,j) 如果 它表示为 S 是 当

。
高桥先生还参与公共工程。K 我正在考虑修建一条新路。 这项建设创造了一条直接连接某些城市的道路。 2 可能有不止一条道路,在这种情况下,我们将添加新道路而不是拆除现有道路。
你的工作是按照给定的顺序建造新道路,每次建造时,你 目的是编写一个程序来计算 S 。
入力
输入将以以下形式通过标准输入给出。
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
- 1 城市和道路的数量显示在第二行。 2 整数 编写一个程序来查找 N (1 ≦ N ≦ 400) 和 将其放在 M (1 ≦M ≦ 1000) 用空格分隔。
- 2 来自行 M 行提供有关现有道路的信息。这几天之一 代表第 i (1≦i≦M) 行中,i 路的信息 3 整数 编写一个程序来查找 A_i(1≦A_i≦N)、 B_i(1≦B_i≦N)、 C_i(1≦C_i≦1,000) 用空格分隔。这是i 第条路是城市 A_i 和 将其放在 B_i 距离 表示它们与 C_i连接。A_i≠B_i ,直接连接同一城市的道路最多。 1 一。
- 城市的任意组合 保证可以到达 (A,B) , 沿着A 的一些道路行驶 保证您可以达到 B 。
- 2+M 第二行显示了新建道路的数量。 写入 K (1≦K≦400) 。
- 3+M 来自行 K 行提供有关新建道路的信息。这几天之一 代表有关 i (1≦i≦K) 行中,i 条新道路的信息 3 整数 编写一个程序来查找 X_i(1≦X_i≦N)、 Y_i(1≦Y_i≦N)、 Z_i(1≦Z_i≦1,000) 以空格分隔。i 城市新路 代表与 X_i 和 将其放在 Y_i 距离 表示它们与 Z_i 连接。X_i≠Y_i 。
出力
应按以下格式输出到标准输出。 新道路建成后所有可能城市之间的最短路线长度之和,直至
i (1≦i≦K) 行中,i 新建道路后所有可能城市之间的最短路线长度总和 S 。
不要忘记结尾的换行符。
入力例1
4 3 1 2 1 2 3 1 3 4 10 2 3 4 1 1 4 1
出力例1
10 8
初始状态如下。

第一次构建后,图表将如下所示:

第二次构建后,图表将如下所示:

入力例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
出力例2
13649 12878 11954 11954 11280 11058 11058 8099 8099 8099