Problem Description

For a connected undirected graph,where every vertex has a value, every edge has a unique weight. We define the limit of a path as the maximum edge weights of all edges on the path. The limiting edge between two vertexes $S(u,v)$ is the edge with the maximum weight in the path,and this path has to be with the minimum limit between two vertexes($S(u,v)=0$ if $u=v$), and the value of $S(u,v)$ is uniquely certain for graphs with edge weights are different.

Define each edge of the limit set $T(w)=${$u|1\leq u\leq n,\exists x: \ S(u,x)=w,val(u)\ge val(w)$} ($x$ is a vertex) $val (u)$ represents the value of vertex $u$, $val (w) $ represents edge $w$ weights.

Now you need to dye each vertex black and white, for the $i$th vertex, the cost of dyeing it black is $a_i$, the cost of dyeing it white is $b_i$, for each edge $w_i$, we need to satisfy that the number of black vertexes in $T(w_i)$ does not exceed $x_i$ and the number of white vertexes does not exceed $y_i$.

What is the minimum dyeing cost if the conditions are met?

Input

The first line input a positive integer $(1\le T\le 5)$, representing the number of test data.

For each test data:

In the first line, input two positive integers $n,m(1\leq n\leq 1000,1\leq m\leq 2000)$, representing the number of vertexes and the number of edges in the graph.

In the next $n$ row, the three positive integers $a_i,b_i,val(i)(0\leq a_i,b_i\leq 10^5,1\leq val(i)\leq m)$represent the cost of dyeing the $i$th vertex black, the cost of dyeing the $i $th vertex white, and the vertex weight.

In the next $m$ row, the three positive integers in each row $u_i,v_i,val(i)(1\leq u_i,v_i\leq n(u\neq v),1\leq val(i)\leq m)$represent an undirected edge and its weight $w_i$.

The next line contains $m$ integers $x_i(0\leq x_i\leq m)$ represents the upper limit on the number of black vertexes in the limit set of $i$ edges.

The next line contains $m$integers $y_i(0\leq y_i\leq m)$ represents the upper limit on the number of white vertexes in the limit set of $i$ edges.

Output

Output an integer representing the minimum cost of dyeing.

It is guaranteed that there is a method that meets the requirements and all edge weights are different.

1
5 5
5 3 3
3 5 2
4 1 1
2 3 2
3 4 1
1 2 3
1 3 1
2 5 2
2 4 4
1 4 5
1 1 1 1 1
1 1 1 1 1

14

Hint

For example

$T(x)$represents the limited set of edges numbered $x$

$T(1)=\{1\}$

$T(2)=\{1,3\}$

$T(3)=\{2\}$

$T(4)=\{\emptyset\}$

$T(5)=\{\emptyset \}$

The optimal solution is to dye vertex 3 white and the remaining vertexes black.