Score : $550$ points

问题陈述

给定一个权重无向连通图 $G$，包含 $N$ 个顶点和 $N-1$ 条边，顶点编号从 $1$ 到 $N$，边编号从 $1$ 到 $N-1$。边 $i$ 连接顶点 $a_i$ 和 $b_i$，权重为 $c_i$。

你需要依次处理 $Q$ 个查询。第 $i$ 个查询描述如下：

• 给定整数 $u_i, v_i, w_i$。在 $G$ 中添加一条连接顶点 $u_i$ 和 $v_i$ 的边，权重为 $w_i$。然后，打印 $G$ 的最小生成树中边的权重之和。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a weighted undirected connected graph $G$ with $N$ vertices and $N-1$ edges, where vertices are numbered $1$ to $N$ and edges are numbered $1$ to $N-1$. Edge $i$ connects vertices $a_i$ and $b_i$ with a weight of $c_i$.

You are given $Q$ queries to process sequentially. The $i$-th query is described as follows:

• You are given integers $u_i, v_i, w_i$. Add an edge with weight $w_i$ between vertices $u_i$ and $v_i$ in $G$. Then, print the sum of the weights of the edges in a minimum spanning tree of $G$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq a_i < b_i \leq N$
• $1 \leq u_i < v_i \leq N$
• $1 \leq c_i, w_i \leq 10$
• The graph is connected before processing the queries.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $Q$

$a_1$ $b_1$ $c_1$

$\vdots$

$a_{N-1}$ $b_{N-1}$ $c_{N-1}$

$u_1$ $v_1$ $w_1$

$\vdots$

$u_Q$ $v_Q$ $w_Q$

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

Sample Input 1

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

Sample Output 1

12
10
10
7

Here is the graph after adding the edge for each query. The edges included in the minimum spanning tree are colored red.

Sample Input 2

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

Sample Output 2

49
46
45
38
34
33