보물 다이빙

전설은 종종 위대한 보물에 대해 이야기하지만, 실제로 그런 보물과 마주칠 기회는 좀처럼 오지 않습니다. 대부분은 바다에 잠기거나 산 밑에 숨겨져 있죠. 하지만 당신이 존경하는 인물 중 하나가 가르쳐 주었듯이, 보물은 박물관에 있어야 합니다. 그리고 이제 당신에게 그 일을 해낼 기회가 왔습니다.

탐사 도중 당신은 거대한 동굴망을 발견했습니다. 현지의 한 주술사는 조상들이 동굴 안에 숨겨 둔 엄청난 보물에 대해 이야기했고, 동굴망과 그 안 보물의 위치가 그려진 오래된 지도까지 건네주었습니다. 안타깝게도 동굴망은 완전히 물에 잠겨 있습니다. 이곳까지 오는 길이 워낙 멀기에, 당신은 짧게 잠수해 동굴망을 정찰해 보기로 합니다. 그런데 입구로 돌아온 순간 소식이 들려옵니다. 근처 화산이 방금 분출한 것입니다. 용암이 동굴망 입구를 뒤덮어 보물이 영영 사라질 것이 거의 확실합니다.

이제 모든 것이 당신에게 달렸습니다. 남은 시간은 아주 짧고, 공기 탱크는 달랑 하나뿐입니다. 잠수는 단 한 번만 할 수 있습니다. 어떤 경로로 가야 할까요? 동굴망은 거대하니, 가능한 한 많은 보물을 구해 내야 합니다. 대학에서 컴퓨터 과학을 공부하던 시절이 떠오르고, 문득 깨닫습니다. 아직 노트북이 있잖아! 프로그램을 짜서 최선의 성과를 계산해 볼 수 있습니다.

동굴 안에서 보물을 찾거나 집어 드는 것, 그리고 동굴을 지나가는 것은 공기를 전혀 소모하지 않는다고 가정해도 됩니다. 오직 터널을 잠수해 통과할 때만 공기가 듭니다.

각 테스트 집합은 여러 개의 테스트 케이스로 이루어집니다. 입력은 한 줄에 하나의 수 t (0 < t ≤ 2000)로 시작하며, 이는 테스트 케이스의 수입니다.

각 테스트 케이스는 한 줄에 두 정수 n과 m으로 시작합니다. n은 동굴의 수, m은 이를 잇는 터널의 수입니다 (1 ≤ n ≤ 10 000; 0 ≤ m ≤ 50 000). 이어지는 m개의 줄은 각각 터널을 세 정수 a, b, l로 설명합니다. a와 b는 동굴이고, l은 그 터널을 잠수해 통과하는 데 필요한 공기의 양입니다 (0 ≤ a, b < n; 0 ≤ l ≤ 500). 터널 다음에는 한 줄에 정수 i가 오며, 이는 동굴망 안 보물(idol)의 개수입니다 (0 ≤ i ≤ 8). 그 뒤에는 보물이 있는 동굴들을 나타내는 i개의 정수 p1, ..., pi가 한 줄에 주어집니다 (0 ≤ p1, ..., pi < n). 테스트 케이스는 하나의 수 a로 끝나며, 이는 당신이 가진 공기의 양(리터)입니다 (0 ≤ a ≤ 1 000 000). 당신은 항상 0번 동굴에서 출발해 0번 동굴로 돌아옵니다.

각 테스트 케이스마다 한 줄에 하나의 수를 출력합니다. 이는 잠수부가 회수할 수 있는 보물의 최대 개수입니다.