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

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

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

输出$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)