You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

​ 小$L$有一棵树，每条边都有边权。定义$dist(x,y)$表示$x$号点到$y$号点的唯一简单路径上的边权和（即$x$和$y$的距离）。现在小$L$想知道：

​ 即树上点两两之间的距离和。然而这个树是会不断变换的，每一次都会有一条边的权值改变。每一次修改之后，小$L$都想知道树上点两两之间的距离和，你可以帮帮他吗？

【输入格式】

​ 输入文件名为tree.in。

​ 第一行有三个正整数$n,q$，分别表示树的点数，和修改的次数。

​ 接下来$n-1$行，每行三个数$x_i,y_i,w_i$，表示编号为$i$的边连接了$x_i$和$y_i$，边权为$w_i$。

​ 接下来$q$行，每行两个数$id_i,w_i$，表示将编号为$id_i$的边的权值改为$w_i$。

【输出格式】

​ 输出文件名为tree.out。

​ 输出共$q$行，第$i$行表示第$i$次修改后树上点两两之间的距离和。

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

12
18

【样例2】

​ 见下发文件。

【数据范围】

​ 对于 $20\%$ 的数据，满足 $n \leq 100,q \leq 100$。

​ 对于 $40\%$ 的数据，满足$n \leq 3000,q \leq 3000$。

​ 另有 $20\%$ 的数据，满足$n \leq 200000,q = 1$。

​ 对于 $100\%$ 的数据，满足 $1 \leq n \leq 200000,1 \leq q \leq 200000,1 \leq w_i \leq 1000$。