### 问题描述 小 $L$ 有一棵树，每条边都有边权。定义 $dist(x,y)$ 表示 $x$ 号点到 $y$ 号点的唯一简单路径上的边权和（即 $x$ 和 $y$ 的距离）。现在小 $L$ 想知道： $$ \sum_{i=1}^{n} \sum_{j=i+1}^{n} dist(i,j) $$ 即树上点两两之间的距离和。然而这个树是会不断变换的，每一次都会有一条边的权值改变。每一次修改之后，小 $L$ 都想知道树上点两两之间的距离和，你可以帮帮他吗？ ### 输入格式 第一行有三个正整数 $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$。 ### 输出格式 输出共 $q$ 行，第 $i$ 行表示第 $i$ 次修改后树上点两两之间的距离和。 ### 样例输入 ``` 4 2 1 2 1 1 3 1 1 4 1 1 2 2 3 ``` ### 样例输出 ``` 12 18 ``` ### 评测数据范围 对于 $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$。