Далекі поїздки на таксі
Водій таксі Накамура був у захваті, адже отримав пасажира, який хотів поїхати в місто, що знаходиться за тисячі кілометрів. Проте він зіткнувся з проблемою. Як відомо, більшість таксі в Японії працюють на зрідженому нафтовому газі (LPG), оскільки це дешевше за бензин. У країні є понад 50,000 автозаправних станцій, але менше одного відсотка з них продають LPG. Хоча бак LPG його автомобіля був повний, його ємність обмежена, і автомобіль проїжджає 10 кілометрів на літр, тому Накамура може не дістатися до місця призначення без дозаправки в дорозі. Він знав усі місця розташування станцій LPG.
Ваше завдання — написати програму, яка визначить найкращий маршрут від поточного місця розташування до місця призначення, не залишаючись без пального.
Вхідні дані
Вхідні дані складаються з кількох наборів, і кожен набір має наступний формат.
N M capsrc destc1;1 c1;2 d1c2;1 c2;2 d2...cN;1 cN;2 dNs1s2...sM
Перший рядок набору даних містить три цілі числа (N, M, cap), де N — кількість доріг (1 ≤ N ≤ 3000), M — кількість станцій LPG (1 ≤ M ≤ 300), і cap — ємність бака (1 ≤ cap ≤ 200) в літрах. Наступний рядок містить назву поточного міста (src) та назву міста призначення (dest). Місто призначення завжди відрізняється від поточного міста.
Наступні N рядків описують дороги, які з'єднують міста. Дорога i (1 ≤ i ≤ N) з'єднує два різні міста c_{i,1} і c_{i,2} з цілою відстанню d_i (0 < d_i ≤ 2000) в кілометрах, і він може їхати з одного міста в інше. Ви можете припустити, що жодні дві різні дороги не з'єднують ту саму пару міст. Стовпці розділені одним пробілом. Наступні M рядків (s_1, s_2, ..., s_M) вказують назви міст зі станцією LPG. Ви можете припустити, що місто зі станцією LPG має принаймні одну дорогу.
Назва міста має не більше 15 символів. Тільки англійський алфавіт ('A' до 'Z' і 'a' до 'z', чутливий до регістру) дозволений для назви.
Рядок з трьома нулями завершує введення.
Вихідні дані
Для кожного набору даних виведіть рядок, що містить довжину (в кілометрах) найкоротшої можливої подорожі від поточного міста до міста призначення. Якщо Накамура не може дістатися до місця призначення, виведіть "-1" (без лапок). Ви не повинні виводити жодних інших символів.
Фактична ємність бака зазвичай трохи більша, ніж зазначено в специфікації, тому ви можете припустити, що він може дістатися до міста, навіть коли залишок пального стає рівним нулю. Крім того, ви завжди можете заправити бак у місці призначення, тому вам не потрібно турбуватися про зворотну подорож.