题目描述

给出一个 n 个点的树，树边有边权。
求所有点对的距离之和
这题看起来很简单,所以...当然不能这么简单了!
我们还需要不断地修改树上的边权,并且需要知道每次修改后所有点对的距离之和
一共修改m次

输入

第一行一个数 n,表示树有n个点
接下来 n-1 行，每行三个数 a、 b、 c，表示有一条连接 a、b 的权值为 c 的边。
接下来一行一个数 m，表示修改次数。接下来 m 行，每行三个数 u、 v、 w，表示
u 到 v 的路径上的每一条边权值都加上 w。

输出

输出 m+1 行， 分别表示 0~m 次操作之后的距离和。
输出结果对1,000,000,007取模

输入样例

3
1 2 2
1 3 1
2
1 2 -2
2 3 1

输出样例

6
2
6

数据范围

对于 20%的数据， n,m≤50
对于 40%的数据， n,m≤300
对于 60%的数据， n,m≤3000
另存在 20%的数据， m=0
对于 100%的数据， n,m≤100000， -10^9≤c,w≤10^9

限制

时间限制1s,空间限制128m