给定一棵包含 $n$ 个顶点的有根树，根节点为 1。考虑树的一种重链剖分（heavy-light decomposition），其中每条边要么是重边（heavy edge），要么是轻边（light edge）。对于每个顶点，在其与所有子节点相连的边中，至多有一条边可以是重边。

在本题中，我们有一个简单路径的多重集 $T$，初始为空。我们将根据 $T$ 将每条边指定为重边或轻边，并满足上述条件。

每次对 $T$ 进行更新时，你的任务是找到一种边的分配方式，使得 $T$ 中每条路径上的轻边数量之和最小。

给定 $q$ 次更新。每次更新包含三个整数：$s$、$e$ 和 $k$。这意味着将 $k$ 条从 $s$ 到 $e$ 的简单路径插入到 $T$ 中。在每次更新后，求出 $T$ 中所有路径上的轻边数量之和的最小值。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $q$ ($2 \le n \le 10^5$; $1 \le q \le 10^5$)。

接下来的 $n-1$ 行，第 $i$ 行包含两个空格分隔的整数 $x_i$ 和 $y_i$，表示第 $i$ 条边连接树中的顶点 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le n$; $x_i \neq y_i$)。保证给定的边构成一棵树。

接下来的 $q$ 行，每行包含三个空格分隔的整数 $s$、$e$ 和 $k$，描述每次更新 ($1 \le s, e \le n$; $s \neq e$; $1 \le k \le 10^9$)。

更新按输入顺序处理。更新是永久性的：每次更新所做的更改在后续更新中依然有效。

输出格式

对于每次更新，在更新后打印一行答案。

样例

样例输入 1

3 3
1 2
3 1
1 3 2
1 3 3
1 2 2

样例输出 1

0
0
2

样例输入 2

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

样例输出 2

0
0
0
0
0

样例输入 3

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

样例输出 3

0
1
7
12
14
15
23
26