Занурення за скарбами
Легенди часто розповідають про великі скарби. Але рідко випадає шанс насправді натрапити на ці скарби. Більшість з них загублені в морі або сховані під горами. Але, як ви дізналися від одного зі своїх найбільших кумирів, скарби повинні бути в музеї. І тепер у вас є шанс це здійснити.
На експедиції ви знайшли велику мережу печер. Місцевий шаман розповів про неймовірні цінності, які його предки сховали в печерах. Він навіть дав вам стародавню карту, на якій зображена мережа печер і місце розташування скарбів у них. На жаль, мережа печер повністю затоплена. Оскільки дорога сюди займає вічність, ви вирішили зробити коротке занурення і розвідати мережу печер. Але, повернувшись до входу в мережу печер, ви отримуєте новину... поруч щойно вивергнувся вулкан. Майже гарантовано, що лава покриє входи до мережі печер, і скарби будуть втрачені назавжди.
Це ставить вас у скрутне становище. У вас залишилося мало часу, і лише один жалюгідний балон з повітрям. Тож усе залежить від вас. У вас є час лише на одне занурення. Але як ви можете вирішити, який маршрут обрати? Мережа печер величезна, і ви повинні спробувати врятувати якомога більше скарбів. Ви згадуєте свої часи як комп'ютерний науковець в університеті... І тоді вас осяює. У вас все ще є ваш ноутбук. Ви могли б написати програму, щоб допомогти вам визначити, як найкраще врятувати скарби.
Ви можете припустити, що ні знаходження, ні підняття скарбу в печері, ні переміщення по печері не споживає повітря.
Вхідні дані
Кожен набір тестів складається з кількох тестових випадків. Файл починається з одного числа 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 замінено на максимальну кількість ідолів, які дайвер може врятувати.