题目描述

一棵树有 $n$ 个节点与 $(n - 1)$ 条边，其中第 $i$ 条边连接节点 $u_i$ 与 $v_i$，权值为 $w_i$。

您需要处理 $q$ 次询问。第 $i$ 次询问可以记为三个整数 $a_i$，$b_i$ 和 $k_i$。本次询问首先临时将第 $a_i$ 条边的权值改为 $b_i$。之后您需要选择 $2k_i$ 个不同的节点 $s_1, s_2, \cdots, s_{k_i}, e_1, e_2, \cdots, e_{k_i}$ 并考虑树上的 $k_i$ 条简单路径，其中第 $p$ 条路径从节点 $s_p$ 出发，到节点 $e_p$ 结束。称一条边是好的，若它被所有 $k_i$ 条路径包含。最大化好边的总权值。

请再次注意，所有询问对权值的修改都是临时的。在每次询问后，您需要把权值恢复原状。

输入格式

每个测试文件仅有一组测试数据。

第一行输入两个整数 $n$ 和 $q$（$2\leq n\leq 5\times 10^5$，$1\leq q\leq 5\times 10^5$）表示节点的数量和询问的数量。

对于接下来的 $(n - 1)$ 行，第 $i$ 行输入三个整数 $u_i$，$v_i$ 和 $w_i$（$1\leq u_i, v_i\leq n$，$1\leq w_i\leq 10^9$）表示第 $i$ 条边连接节点 $u_i$ 和 $v_i$，权值为 $w_i$。

对于接下来的 $q$ 行，第 $i$ 行输入三个整数 $a_i$，$b_i$ 和 $k_i$（$1 \le a_i \le n - 1$，$1 \le b_i \le 10^9$，$1 \le k_i \le \lfloor\frac{n}{2}\rfloor$）表示第 $i$ 次询问。

输出格式

每次询问输出一行一个整数表示答案。

7 3
1 2 20
2 3 10
2 4 40
4 6 10
1 5 30
5 7 10
2 100 1
5 50 2
2 100 3

160
110
20

提示

对于第一次询问，选择 $s_1 = 3$ 和 $e_1 = 7$。

对于第二次询问，选择 $s_1 = 4$，$s_2 = 6$，$e_1 = 7$ 和 $e_2 = 5$。

对于第三次询问，选择 $s_1 = 3$，$s_2 = 4$，$s_3 = 6$，$e_1 = 5$，$e_2 = 1$ 和 $e_3 = 7$。