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

高桥君是 Atcoder 王国的国王。Atcoder 王国包括 $N$ 个城市（编号 $1\sim N$）和 $m$ 条双向的道路。每条道路都有长度。对于 Atcoder 王国中的任意城市组合 $(A,B)$，都可以保证从 $A$ 到 $B$ 有多条道路。 高桥君认为，Atcoder 人的幸福在很大程度上取决于交通的便利性。为了找出人们的幸福程度，他想找到所有可能城市之间最短路径长度的总和 $S$。 如果城市 $i,j$ 之间的最短路径的长度为 $D(i,j)$，则 $$ S=\sum_{i=1}^N\sum_{j=i+1}^ND(i,j) $$ 高桥先生正计划建造 $K$ 条新道路作为公共项目。这样的建设可能会导致多于两条或两条直接连接城市的道路，在这种情况下，现有道路将不会被拆除，而是会被增加。 您的任务是按照给定的顺序建造一条新路，并编写一个程序来计算上述每种施工的 $S$。

第一行两个数 $n$ 和 $m$，分别表示城市数和道路数。 接下来 $2\sim m+1$ 行每行三个整数 $u,v,w$，表示有一条连接 $u,v$ 城市的长度为 $w$ 的路径。 第 $m+2$ 行一个整数 $k$，表示有 $k$ 条新的路要修建。 第 $m+3\sim m+k+2$ 行每行三个整数 $x,y,z$，表示又要建一条连接 $x,y$ 的长度为 $z$ 的路径。

输出 $k$ 行，第 $i$ 行一个整数，表示在修完第 $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)