Servicing Clients

One facility and several clients sit at some of the vertices of a weighted graph $G = (V, E)$. Every client $j$ comes with a nonnegative demand $d_j$ and a nonnegative priority $p_j$ that says how important that client is.

The servicing cost of client $j$ is $c_j \times d_j$, where $c_j$ is the shortest distance in $G$ from the facility vertex to the vertex of client $j$. In the figure below the servicing cost of client $a$ is $3 \times d_a$, where $d_a$ is the demand of client $a$. The servicing cost of client $b$ in the same figure is infinite, because no path connects client $b$ to the facility.

Write a program that picks a subset of the client set whose total servicing cost stays within a nonnegative budget $B$ and whose total priority is as large as possible.

Your program reads from standard input. The first line contains the number of test cases $T$. ($1 \le T \le 20$)

Each test case starts with a line containing the number of vertices $N$ of the graph. ($1 \le N \le 100$) The vertices are numbered from $0$ to $N-1$, and the facility sits at vertex $0$.

The next line contains the number of clients $M$. ($0 \le M \le 100$) Each of the next $M$ lines describes one client with three integers: the vertex the client sits at, the demand, and the priority. The vertex number is between $0$ and $N-1$, and the demand and the priority are each between $0$ and $100$.

The next line contains the total budget $B$. ($0 \le B \le 100$)

The next line contains the number of edges $L$. ($0 \le L \le 100$) Each of the next $L$ lines describes one edge with three integers: the two vertices the edge joins, then the cost of the edge. The vertex numbers are between $0$ and $N-1$ and the cost is between $0$ and $100$. Edges have no direction.

Your program writes to standard output. For each test case, print one line with the total priority of the clients selected for service.