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 xi is equal to or smaller than ri. Additionally, the i-th flower's value is vi.
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≤T≤500) representing the number of test cases.
For each test case, the first line contains two positive integers n,m(1≤n,m≤105), the number of nodes and roses.
The i-th line of the following n−1 lines contains two positive integers ui,vi,representing a branch in the tree which links node ui and vi.
The i-th line of the following m lines contains three non-negative integers xi,ri,vi(1≤xi≤n,1≤ri,vi≤109), 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.