Description

There are $n$ towns in Byteland, labeled by $1, 2, \dots, n$, connected by $n - 1$ bidirectional roads like a tree. $m$ tourists are going to visit Byteland, the $i$-th of which will start his journey at the $s_i$-th town. However, none of them has decided where to end his journey. Formally, for the $i$-th tourist, he has made $3$ plans, the $j$-th of which will end at the $e_{i,j}$-th town, and will cost him $c_{i,j}$ dollars. When a tourist makes his decision, he will walk along the shortest path to visit all the towns from $s_i$ to his destination. Note that $e_{i,j}$ can coincide with $s_i$, the $s_i$-th town and the destination town will also be visited by the $i$-th tourist. Two plans may share the same destination but may differ in cost because the tourist may do extremely different things in the same town.

They will share photos of their journeys in Byteland. Nobody is willing to visit the same place with others. Your task is to help each tourist choose his destination from his plans such that each town will be visited by at most one tourist, and the total cost for all the tourists is minimized, or determine it is impossible.

Format

Input

The first line contains a single integer $T$ ($1 \leq T \leq 500$), the number of test cases. For each test case:

The first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 200\,000$, $1\leq m\leq 100\,000$), denoting the number of towns and the number of tourists.

Each of the next $n-1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$), denoting a bidirectional road between $u_i$ and $v_i$. It is guaranteed that the roads form a tree.

In the next $m$ lines, the $i$-th line contains seven integers $s_i$, $e_{i,1}$, $c_{i,1}$, $e_{i,2}$, $c_{i,2}$, $e_{i,3}$ and $c_{i,3}$ ($1\leq s_i,e_{i,j}\leq n$, $1\leq c_{i,j}\leq 10^6$), describing the $i$-th tourist.

It is guaranteed that the sum of all $n$ is at most $1\,000\,000$, and the sum of all $m$ is at most $300\,000$.

Output

For each test case, print a single line containing an integer denoting the minimum total cost. If there is no solution, print ''$\texttt{-1}$'' instead.

Samples

2
7 2
1 2
1 3
2 4
2 5
3 6
3 7
2 1 1 3 100 4 200
3 2 1 4 2 7 50
4 2
1 2
2 3
3 4
1 2 1 3 1 4 1
2 1 1 3 1 4 1

51
-1