Treasure

Problem Description

?? 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?

Input

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

Output

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.

Sample Input

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

Sample Output

Case #1: 100
Case #2: 8

Author

FZU

Source

2016 Multi-University Training Contest 4