AT_arc035_c [ARC035C] アットコーダー王国の交通事情

[problemUrl]: https://atcoder.jp/contests/arc035/tasks/arc035_c 高橋くん様は、アットコーダー王国の王様です。彼が統治するアットコーダー王国は、$ 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 $ を出力せよ。 末尾の改行を忘れないこと。

### Sample Explanation 1 初期状態は以下の通りです。 !\[\](http://arc035.contest.atcoder.jp/img/arc/035/C\_sample1\_1.png) 一度目の建設の直後、グラフは以下のようになります。 !\[\](http://arc035.contest.atcoder.jp/img/arc/035/C\_sample1\_2.png) 二度目の建設の直後、グラフは以下のようになります。 !\[\](http://arc035.contest.atcoder.jp/img/arc/035/C\_sample1\_3.png)