题目描述：

高桥君是 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$。