题目描述

在一片神秘的 “连通之森” 中，有 $N$ 座魔法塔（编号为 $1$ 到 $N$），初始时塔与塔之间由 $N−1$ 条古老的魔法通道相连，每条通道都有一个维持其运转的魔力值 $c_i$。整个森林的魔法网络是连通的，因此所有塔之间原本都能通过现有通道相互抵达。

最近，森林中出现了 $Q$ 次魔力潮汐。每次潮汐会引发一道新的魔法波动，在两个指定塔 $u_i$ 与 $v_i$ 之间临时生成一条新的魔法通道，其魔力消耗为 $w_i$。新通道出现后，整个魔法网络会立刻重组——森林将自动选择魔力总消耗最小的通道组合，使得所有塔保持连通（即形成最小生成树），而多余的通道会因魔力过载而消失。

作为森林的守护者，你需要在每次魔力潮汐后，立即计算出当前网络最小生成树的总魔力消耗，并记录下来。

输入格式

第一行两个整数 $N$（魔法塔数量）和 $Q$（魔力潮汐次数）。

接下来 $N−1$ 行，每行三个整数 $a_i,\ b_i,\ c_i$，表示初始连接塔 $a_i$ 与塔 $b_i$ 的通道及其魔力消耗。

随后 $Q$ 行，每行三个整数 $u_i,\ v_i,\ w_i$，描述一次魔力潮汐生成的新通道信息。

输出格式

输出共 $Q$ 行，每行一个整数，表示对应潮汐发生后，整个魔法网络最小生成树的总魔力消耗。

样例

4 4
1 2 6
2 3 5
2 4 4
1 3 3
1 2 3
1 4 10
3 4 1

12
10
10
7

8 6
1 8 8
1 6 10
1 5 8
2 6 6
6 7 6
1 3 9
2 4 7
1 3 4
1 6 7
3 4 6
1 5 1
7 8 4
3 5 3

49
46
45
38
34
33

样例1解释

下图展示了每次查询后添加边的情况。最小生成树中的边用红色标记。

数据范围

对于 $40\%$ 的数据，$2\le N\le 1000$，$1\le Q\le1000$。

对于 $100\%$ 的数据，$2\le N\le 2\times 10^5$，$1\le Q\le 2\times10^5$，$1\le a_i<b_i\le N$，$1\le u_i<v_i\le N$，$1\le c_i,\ w_i\le 10$。