C - アットコーダー王国の交通事情 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くん様は、アットコーダー王国の王様です。彼が統治するアットコーダー王国は、1 から N までの番号が付けられた N 個の都市とそれらを結ぶ双方向に行き来可能な M 本の道路からなります。それぞれの道路には長さがあります。 アットコーダー王国の任意の都市の組み合わせ (A,B) について、A からいくつかの道路を辿って B に辿り着けることが保障されています。

高橋くん様は、アットコーダー国民の幸せが、交通の利便性に大きく依存していると考えています。 国民がどれくらい幸せかを調べるために、ありうる全ての都市間の最短経路長の総和 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