题目描述

给定一棵树。树上点有点权，边有边权。

边权是固定且为正的，点权初始为 $0$。

给你 $q$ 次操作，每次操作形如将某个点的点权加上某个值（可能是负值）。保证点权始终非负。

你要在每次操作后输出整棵树的带权重心到所有节点的带权距离和。

形式化的，定义 ${\rm dist}(u,v)$ 为树上 $u,v$ 间简单路径的边权之和，$a_p$ 为 $p$ 点的当前点权，你要求出：

$$\min\left\{\sum_{1\le v\le n} {\rm dist}(u,v) \times a_v \ \middle|\ 1\le u\le n\right\} $$

---

输入格式

第一行两个数 $n$ 和 $q$，分别表示树的点数和操作的个数，其中点从 $1$ 到 $n$ 标号。

接下来 $n-1$ 行，每行三个正整数 $u,v,w$，表示 $u$ 和 $v$ 之间有一条边权为 $w$ 的边。

接下来 $q$ 行，每行两个数 $u,e$，表示将 $u$ 点点权加上 $e$。

数据保证任何时刻每个点上的点权都是非负的。

---

输出格式

每个操作后输出一行，表示此时答案。

---

样例

输入：

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

输出：

0
1
4
5
6

---

数据范围

本题与原题的差异仅在于：

• 缩小数据范围 & 时间限制（防止卡评测）
• 空间限制改为 512MB
• 取消每个点的度数限制

欢迎投递 hack 数据的 Generator。