关于本题

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

• 缩小数据范围 & 时间限制。（防止卡评测，如果被卡常了我很抱歉）
• 空间限制改为 512MB。
• 取消每个点的度数限制。

欢迎投递 hack 数据的 Generator。

题目描述

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

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

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

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

形式化的，定义 ${\rm dist}(u,v)$ 为树上 $u,v$ 间简单路径的边权之和，$a_p$ 为 $p$ 点的当前点权，你要求出 $\min\{\sum_{1\le v\le n}{\rm dist}(u,v)\times a_v|1\le u\le n\}$。

输入格式

第一行两个数 $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

这份样例与原题相同。

数据范围与提示

对于所有数据，$1\le w\le10^3$，$-10^3\le e\le10^3$，$1\le n,q\le6\times10^4$。

请注意，本题不对树上每个点的度数做出任何保证；即，每个节点的度数可能很大也可能很小。

数据范围、强度有梯度。