Flower

Notice：Don't output extra spaces at the end of one line.

Koishi loves flowers, especially Subterranean Roses.

The rose tree consists of $n$ nodes and $n-1$ branches. You can imagine the structure of the tree as an undirected tree. There are $m$ roses blossom, and Koishi wants to pick some of them. The $i$-th rose contains the node $u$ if and only if the distance from $u$ to $x_i$ is equal to or smaller than $r_i$. Additionally, the $i$-th flower's value is $v_i$.

Koishi wants to maxmize the sum of values of picked roses. However, she doesn't like broken rose, so any two of her picked roses can't intersect. Two roses intersect if and only if there exists at least one node $u$ belongs to both of them.

So what's the largest sum of values of picked roses Koishi can get?

The first line contains a positive integer $T(1\leq T\leq 500)$ representing the number of test cases.

For each test case, the first line contains two positive integers $n,m(1\leq n,m\leq 10^5)$, the number of nodes and roses.

The $i$-th line of the following $n-1$ lines contains two positive integers $u_i,v_i$,representing a branch in the tree which links node $u_i$ and $v_i$.

The $i$-th line of the following $m$ lines contains three non-negative integers $x_i,r_i,v_i(1\leq x_i\leq n,1\leq r_i,v_i\leq 10^9)$, describing the $i$-th rose.

There are at most $12$ test cases with $n+m>2000$

For each test case, ouput one line with one non-negative integer as the largest sum of values.

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

2

2020 Multi-University Training Contest 7