고객 서비스 계획

가중 그래프 $G = (V, E)$의 정점 몇 곳에 시설 하나와 여러 고객이 있다. 고객 $j$마다 음이 아닌 수요 $d_j$와 그 고객의 중요도를 나타내는 음이 아닌 우선순위 $p_j$가 주어진다.

고객 $j$의 서비스 비용은 $c_j \times d_j$이다. 여기서 $c_j$는 그래프 $G$에서 시설이 있는 정점부터 고객 $j$가 있는 정점까지의 최단 거리다. 예를 들어 아래 그림에서 고객 $a$의 서비스 비용은 $3 \times d_a$이고, $d_a$는 고객 $a$의 수요다. 같은 그림에서 고객 $b$는 시설까지 가는 경로가 없으므로 서비스 비용이 무한대다.

고객 집합의 부분집합 중에서, 그 부분집합에 속한 고객의 서비스 비용 합이 음이 아닌 예산 $B$를 넘지 않으면서 우선순위 합이 가장 큰 경우를 찾는 프로그램을 작성하시오.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 20$)

각 테스트 케이스의 첫째 줄에는 그래프의 정점 개수 $N$이 주어진다. ($1 \le N \le 100$) 정점 번호는 $0$부터 $N-1$까지이며, $0$번 정점에 시설이 있다.

다음 줄에는 고객의 수 $M$이 주어진다. ($0 \le M \le 100$) 이어지는 $M$개 줄에는 고객 한 명의 정보가 정수 세 개로 주어진다. 차례대로 고객이 있는 정점 번호, 수요, 우선순위다. 정점 번호는 $0$ 이상 $N-1$ 이하이고, 수요와 우선순위는 각각 $0$ 이상 $100$ 이하다.

다음 줄에는 전체 예산 $B$가 주어진다. ($0 \le B \le 100$)

다음 줄에는 간선의 개수 $L$이 주어진다. ($0 \le L \le 100$) 이어지는 $L$개 줄에는 간선 하나의 정보가 정수 세 개로 주어진다. 앞의 두 정수는 간선이 잇는 두 정점의 번호이고, 세 번째 정수는 간선의 비용이다. 정점 번호는 $0$ 이상 $N-1$ 이하이고, 비용은 $0$ 이상 $100$ 이하다. 간선에는 방향이 없다.

출력은 표준 출력으로 한다. 테스트 케이스마다 서비스 대상으로 고른 고객의 우선순위 합을 한 줄에 하나씩 출력한다.