Problem Statement

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

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

都市 $i$ と $j$ の間の最短経路長を $D(i,j)$ とすれば $S$ は、

と表されます。

また、高橋くん様は公共事業で、$K$ 本の新たな道路を建設しようと思っています。 この建設によって、ある都市間を直接結ぶ道路が $2$ 本以上存在してしまうことがありますが、その場合、既にある道路は取り壊さず、新しく追加します。

あなたの仕事は、新たな道路を与えられた順番に建設していき、建設の度に前述の $S$ を計算するプログラムを書くことです。

Input

入力は以下の形式で標準入力から与えられる。

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$ である。

Output

出力は以下の形式で標準出力に行うこと。

$i (1≦i≦K)$ 行目には、$i$ 番目までの新たな道路を建設した直後の、ありうる全ての都市間の最短経路長の総和 $S$ を出力せよ。

末尾の改行を忘れないこと。