Coloration

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.

Sample Input

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

Sample Output

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.

Source

2023“钉耙编程”中国大学生算法设计超级联赛（6）