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 vertexesS(u,v)=0 if u=v), and the value ofS(u,v) is uniquely certain for graphs with edge weights are different.
Define each edge of the limit set T(w)={u∣1≤u≤n,∃x: S(u,x)=w,val(u)≥val(w)} (x is a vertex) val(u) represents the value of vertexval(w) represents edge w weights.
Now you need to dye each vertex black and white, for the ith vertex, the cost of dyeing it black is ai, the cost of dyeing it white is bi, for each edge wi, we need to satisfy that the number of black vertexes in T(wi) does not exceed xi and the number of white vertexes does not exceed yi.
What is the minimum dyeing cost if the conditions are met?
The first line input a positive integer (1≤T≤5), representing the number of test data.
For each test data:
In the first line, input two positive integers n,m(1≤n≤1000,1≤m≤2000), representing the number of vertexes and the number of edges in the graph.
In the next n row, the three positive integers ai,bi,val(i)(0≤ai,bi≤105,1≤val(i)≤m)represent the cost of dyeing the ith vertex black, the cost of dyeing the ith vertex white, and the vertex weight.
In the next m row, the three positive integers in each rowui,vi,val(i)(1≤ui,vi≤n(u=v),1≤val(i)≤m)represent an undirected edge and its weight wi.
The next line contains m integers xi(0≤xi≤m) represents the upper limit on the number of black vertexes in the limit set of i edges.
The next line contains mintegers yi(0≤yi≤m) represents the upper limit on the number of white vertexes in the limit set of i edges.
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 114
For example
�(�)T(x)represents the limited set of edges numbered �x
�(1)=1T(1)=1
�(2)=1,3T(2)=1,3
�(3)=2T(3)=2
�(4)=∅T(4)=∅
�(5)=∅T(5)=∅
The optimal solution is to dye vertex 3 white and the remaining vertexes black.