You have a rooted tree with $n$ vertices numbered from $\mbox{1}$ through $n$ where the root is vertex $\mbox{1}$.

You are given $m$ triplets, the $j^{th}$ triplet is denoted by three integers $u_j,v_j,c_j$. The $j^{th}$ triplet represents a simple path in the tree with endpoints in $u_i$ and $v_i$ such that $u_j$ is ancestor of $v_j$. The cost of the path is $c_j$.

You have to select a subset of the paths such that the sum of path costs is maximum and the $i^{\mbox{th}}$ edge of the tree belongs to at most $d_i$ paths from the subset. Print the sum as the output.

Input Format

The first line contains a single integer, $\mathbf{T}$, denoting the number of testcases. Each testcase is defined as follows:

The first line contains two space-separated integers, $n$ (the number of vertices) and $m$ (the number of paths), respectively.
Each line $\boldsymbol{i}$ of the $n-1$ subsequent lines contains three space-separated integers describing the respective values of $a_i$, $b_i$, and $d_i$ where ($a_i$, $b_i$) is an edge in the tree and $d_i$ is maximum number of paths which can include this edge.
Each line of the $m$ subsequent lines contains three space-separated integers describing the respective values of $u_j$, $v_j$, and $c_j$ ($u_j\neq v_j$) that define the $j^{th}$ path and its cost.

Constraints

Let $\mbox{M}$ be the sum of $m$ over all the trees.
Let $\mbox{D}$ be the sum of $n\times m$ over all the trees.
$1\leq T\leq10^3$
$1\leq M,m\leq10^3$
$1\leq D,n\leq5\times10^5$
$1\leq c_i\leq10^9$
$1\leq d_j\leq m$

Output Format

You must print $\mathbf{T}$ lines, where each line contains a single integer denoting the answer for the corresponding testcase.

Sample Input
1
8 8
1 2 3
1 3 1
2 4 5
2 5 1
2 6 1
3 7 2
4 8 1
1 2 3
2 8 5
1 8 7
1 5 8
1 6 10
3 7 5
1 7 6
1 7 6

Sample Output
37

Explanation

One of the possible subsets contains paths $1,2,4,5,6,7$. Its total cost is $3+5+8+10+5+6=37$.

见题面

见题面