Сокровища под водой
Легенды часто рассказывают о великих сокровищах, но редко выпадает шанс действительно наткнуться на них. Большинство из них потеряны в море или скрыты под горами. Однако, как вы узнали от одного из своих кумиров, сокровища должны находиться в музее. И теперь у вас есть шанс сделать это возможным.
Во время экспедиции вы обнаружили обширную сеть пещер. Местный шаман поведал вам о невероятных ценностях, которые его предки спрятали в этих пещерах, и даже дал древнюю карту, показывающую сеть пещер и расположение сокровищ. К сожалению, вся сеть пещер затоплена. Поскольку дорога сюда заняла много времени, вы решили сделать короткое погружение, чтобы исследовать сеть. Но, вернувшись к входу, вы узнаете новость... неподалеку извергся вулкан. Почти наверняка лава покроет входы в пещеры, и сокровища будут потеряны навсегда.
Это ставит вас в трудное положение. У вас осталось совсем немного времени и всего один неисправный баллон с воздухом. Теперь все зависит от вас. У вас есть время только на одно погружение. Но как выбрать правильный маршрут? Сеть пещер огромна, и вам определенно стоит попытаться спасти как можно больше сокровищ. Вы вспоминаете свои университетские времена, когда изучали информатику... И тут вас осеняет. У вас все еще есть с собой ноутбук. Вы могли бы написать программу, чтобы помочь вам определить, как лучше всего спасти сокровища.
Вы можете предположить, что ни поиск, ни сбор сокровищ в пещере, ни перемещение по пещере не требуют воздуха.
Входные данные
Каждый набор тестов состоит из нескольких тестовых случаев. Файл начинается с одного числа t (0 < t ≤ 2000) в одной строке, обозначающего количество тестовых случаев в файле. Каждый тестовый случай начинается с двух целых чисел n и m в одной строке, где n — количество пещер, а m — количество соединительных туннелей в сети (1 ≤ n ≤ 10000, 0 ≤ m ≤ 50000). Далее следуют m строк, описывающих туннели пещеры в виде трех целых чисел a b и l, где a, b обозначают пещеры, а l указывает количество воздуха, необходимое для погружения через туннель (0 ≤ a, b < n, 0 ≤ l ≤ 500). После описания туннелей идет целое число i в одной строке, обозначающее количество идолов в системе пещер (0 ≤ i ≤ 8). Затем следует одна строка, содержащая i целых чисел p_1, ..., p_i, обозначающих пещеры, в которых находятся идолы (0 ≤ p_1, ..., p_i < n). Ввод завершается одним числом, обозначающим количество литров воздуха, которое у вас есть (0 ≤ a ≤ 1000000). Вы всегда начинаете (и заканчиваете) в узле с меткой 0.
Выходные данные
Для каждого тестового случая выведите число X в одной строке, где X — это максимальное количество идолов, которые дайвер может спасти.