Treasure

?? has got a treasure map,the treasure map consists of N nodes,there are N-1 bidirectional roads, Each of them connects a pair of nodes,the N nodes are all connected by the N-1 bidirectional roads.?? can travel through the roads.
There are M treasures in some node. Each treasure has a value, treasures are put into boxs,each treasure corresponds to a box and each box corresponds to a key which is also in some node. Now ?? wants to plan a simple path, the path’s start point is node A,and the path’s destination is node B,?? will go from node A to node B. When ?? goes through a node(including node A and node B), he must first collects all keys, and then must open the boxes he can open in this node. The keys he got never disappear during the travel. Now ?? wants to know the maximum value he could get if he plan a best path.Can you help him?

The first line of the input gives the number of case T,T test cases follow.
Each case first line contains two integer n,m(n,m<=100000)indicating the number of nodes and the number of treasures.
Next n-1 lines each line contains two numbers ui and vi(1<=ui,vi<=n) indicates that there’s one road connecting node ui node vi.
Next m lines each line contains three number ui,vi,wi(1<=ui,vi<=n,-1000<=wi<=1000) indicates the position of ith-box’s key and the position of ith-box, and the value of treasure in the ith-box.

T<=30
The sum of n in all the test cases is no more than 600000
The sum of m in all the test cases is no more than 600000

For each that case output”Case #x: y”,where x is the test case number(starting from 1),and y is the answer you get for that case.

2
4 2
1 2
2 3
3 4
1 1 100
2 4 -5
4 3
1 2
1 3
1 4
2 1 1
1 3 2
1 3 5

Case #1: 100
Case #2: 8

FZU

2016 Multi-University Training Contest 4