题目描述

Berland 有 $n$ 个城市和 $m$ 条双向道路。每条道路连接两个不同城市，并具有一个当前维修费用。任意两个城市之间至多有一条道路，并且整张图始终连通。

政府希望选择若干道路进行维修，使得仅使用这些维修后的道路就能从任意城市到达任意其他城市，并且总维修费用最小。显然，这个最小费用就是当前边权下最小生成树的总权值。

未来有 $t$ 天。每天恰好有一条道路的维修费用发生变化；同一条道路可以在不同日期被多次修改。

对于每一天，在当天的费用修改完成后，请输出当前道路网络最小生成树的总权值。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $x_i,y_i,p_i$，表示第 $i$ 条道路连接城市 $x_i,y_i$，初始维修费用为 $p_i$。道路按照输入顺序编号为 $1\sim m$。

然后一行一个整数 $t$，表示修改次数。

接下来 $t$ 行，每行两个整数 $e_i,c_i$，表示把第 $e_i$ 条道路的维修费用修改为 $c_i$。修改是永久的，后续操作在新的费用基础上继续进行。

输出格式

输出 $t$ 行，第 $i$ 行一个整数，表示第 $i$ 天修改完成后当前最小生成树的总权值。

数据范围

$2\le n\le40000$，$n-1\le m\le40000$。

$1\le p_i,c_i\le40000$。

$1\le t\le40000$。

样例 1

样例输入

4 6
1 2 10
2 3 20
2 4 30
1 3 40
3 4 50
4 1 60
3
4 22
5 17
4 14

样例输出

60
47
41

样例 2

样例输入

3 3
3 2 4
3 1 4
2 1 3
3
2 5
2 2
2 5

样例输出

7
5
7