给定一棵包含 $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, \dots, s_{k_i}, e_1, e_2, \dots, e_{k_i}$，并考虑树上的 $k_i$ 条简单路径，其中第 $p$ 条路径的起点为 $s_p$，终点为 $e_p$。如果一条边被所有 $k_i$ 条路径包含，则称该边为“好边”。请最大化所有好边的权重之和。

再次注意，每次询问对权重的修改是临时的。在每次询问后，你需要将权重恢复为原来的值。

输入格式

每个测试文件中仅包含一组测试数据。

第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 5 \times 10^5, 1 \le q \le 5 \times 10^5$)，分别表示顶点数和询问数。

接下来的 $(n-1)$ 行中，第 $i$ 行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le 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$ 个询问。

输出格式

对于每个询问，输出一行，包含一个整数，表示答案。

样例

输入 1

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

输出 1

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$。