#9 「 听风 」

统计

小M喜欢听风的声音。

小M总共有$N$个花园,它们构成了一棵$1$号节点为根的有根树,所有边权均为$1$。定义一个点$x$的$val[x]=\min\{y|y属于x的子树\}$。

从第$1$时刻到第$N$时刻,每一时刻小M会从$1$号节点出发,按照一定的规则拜访一个花园(这个花园是确定的):

1.如果小M在$i$号节点,它是叶子节点或者所有儿子都被拜访过则停在该节点。

2.如果第$i$号节点存在儿子没有拜访过,则找到所有未拜访的儿子中$val$最小的儿子继续行走。

3.小M会拜访最终停在的花园,且每次拜访后会返回一号节点。

因为路程的原因小M的心情点数会减去$1$号节点到拜访节点的距离。因为走路会很累,所以小M可以在任意时刻停止拜访花园

在花园中共有$M$阵和风吹过,每阵风会遍历$x[i],y[i]$这条链上的所有花园,且有$z[i]$的声音舒适度。最终小M的心情点数会加上$\max(size[i]-1,0)*z[i]$,$size[i]$表示小M最终拜访过的花园在这条链上的个数。

请问在什么时候停止拜访,小M的心情值最高呢。

输入格式

第一行两个整数$N$,$M$。

接下来$N-1$行,每行两个整数$x$,$y$,表示$x$与$y$间有一条边。

接下来$M$行,每行三个整数$x$,$y$,$z$,意义如题目所述。

输出格式

一行一个整数表示小M的最高心情值。

样例数据

input

6 3
3 5
2 5
1 2
6 3
4 5
3 4 4
5 6 3
3 6 2

output

4

样例解释

拜访的顺序是:6 3 4 5 2 1

数据规模与约定

对于5-6的测试点:保证i与i+1相连。

对于1-4的测试点:$N \le 1000, M \le 1000$

对于5-10的测试点:$N \le 100000, M \le 100000$

对于1-10的测试点,$z \le 100000$。

时间限制:1s

空间限制:512MB

Author: MirrorGray