Problem F: 东来紫气满函关

Problem F: 东来紫气满函关

Time Limit: 4 Sec  Memory Limit: 256 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

李将军最近还有一个麻烦事,正好碰到了善于计算的叶书生。

函谷关是通往长安的重要旅游景点。

在李将军等名将的领导下,太平无忧,昔日的要塞已经变成了前往长安路上的必游之地。

为了淡化函谷关的军事感,新任工部侍郎欧阳微(字晓栋)决定将函谷关的道路染成紫色,在长安东侧,以取“紫气东来”之祥瑞。

函谷关道路系统可以看作一个树,规定根节点为停车场所在地,在停车场我们有若干台牛车。

每台牛车均从停车场出发,开到节点v(该过程无需花费),然后付出ci的花费把结点vw的道路染成紫色,该过程不重复经过同意节点。(可以理解为对于所有的vw,都有vw的祖先。)

虽然大唐很有钱,但是玄宗不愿浪费人民的劳动成果,他责令欧阳尚书选出花费最少的方案,使得所有的道路都被染成紫色。

欧阳尚书对李将军说“你曾经也是驻守在这里的一名伍长,看你对这里有很深的感情,这个难题就交给你了”。

谁不知道欧阳尚书就是超级计算机的管理员啊!李将军无奈,找到了叶书生。

叶书生说“其实我可以随时和超级计算机通信,但现在欧阳尚书从中作梗,这个问题怕是得你来了“。

李将军找到了你,并许诺你解出来之后可以去大唐东市喝GoGo奶茶,他买单。

Input

输入仅一组数据

对于每一组数据,第一行包含两个整数nm1<=nm<=300000),表示这棵树有n个节点,共有m辆牛车。

接下来的n-1行中的每一行包含两个整数v1v2,表示v1v2联通。

接下来的m行中的每一行包含三个整数wvc,表示第i台牛车从停车场出发,先开到v点,然后花费c1<=c<=1000000000)将vw的道路染成紫色。

Output

对于每一组数据,输出仅一行,输出最小将所有道路染成紫色的花费。

Sample Input

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

Sample Output

6

HINT

[Submit][Status]