Uzun Məsafəli Taksi
Nakamura adlı bir taksi sürücüsü, uzaq bir şəhərə getmək istəyən bir sərnişin aldığı üçün çox sevinir. Lakin bir problem var: Yaponiyada əksər taksilər benzinə nisbətən daha ucuz olduğu üçün maye qaz (LPG) ilə işləyir. Ölkədə 50,000-dən çox yanacaqdoldurma məntəqəsi olsa da, onların yalnız kiçik bir faizi LPG satır. Avtomobilinin LPG çəni dolu olsa da, çənin tutumu məhduddur və avtomobil hər litr üçün 10 kilometr gedir. Bu səbəbdən, yolda çəni doldurmadan təyinat yerinə çata bilməyə bilər. Nakamura, LPG məntəqələrinin bütün yerlərini bilir.
Sizin vəzifəniz, mövcud yerdən təyinat yerinə yanacaq bitmədən ən yaxşı yolu tapacaq bir proqram yazmaqdır.
Giriş verilənləri
Giriş bir neçə datasetdən ibarətdir və hər bir dataset aşağıdakı formatdadır.
N M cap src dest c1;1 c1;2 d1 c2;1 c2;2 d2 ... cN;1 cN;2 dN s1 s2 ... sM
Bir datasetin ilk sətri üç tam ədəddən (N, M, cap) ibarətdir, burada N yolların sayı (1 ≤ N ≤ 3000), M LPG məntəqələrinin sayı (1 ≤ M ≤ 300), və cap çənin tutumu (1 ≤ cap ≤ 200) litr ilədir. Növbəti sətr cari şəhərin (src) və təyinat şəhərinin (dest) adını ehtiva edir. Təyinat şəhəri həmişə cari şəhərdən fərqlidir.
Növbəti N sətr şəhərləri birləşdirən yolları təsvir edir. Yol i (1 ≤ i ≤ N) iki fərqli şəhəri c_{i,1} və c_{i,2} bir tam məsafə d_i (0 < d_i ≤ 2000) kilometr ilə birləşdirir və hər iki şəhərdən digərinə gedilə bilər. Eyni şəhər cütünü birləşdirən iki fərqli yol olmadığını qəbul edə bilərsiniz. Sütunlar bir boşluq ilə ayrılır. Növbəti M sətr (s_1, s_2, ..., s_M) LPG məntəqəsi olan şəhərlərin adlarını göstərir. LPG məntəqəsi olan bir şəhərin ən azı bir yolu olduğunu qəbul edə bilərsiniz.
Bir şəhərin adı 15 simvoldan çox deyil. Şəhərin adı üçün yalnız İngilis əlifbası ('A'-dan 'Z'-ə və 'a'-dan 'z'-ə, böyük-kiçik hərf həssas) icazə verilir.
Üç sıfırdan ibarət bir sətr girişi bitirir.
Çıxış verilənləri
Hər bir dataset üçün, cari şəhərdən təyinat şəhərinə mümkün olan ən qısa səfərin uzunluğunu (kilometr ilə) ehtiva edən bir sətr çıxarın. Əgər Nakamura təyinat yerinə çata bilmirsə, "-1" (tırnaq işarələri olmadan) çıxarın. Başqa heç bir simvol çıxarmamalısınız.
Əsl çən tutumu adətən spesifikasiya vərəqində göstəriləndən bir az böyükdür, buna görə də qazın qalan miqdarı tam sıfır olduqda belə bir şəhərə çata biləcəyini qəbul edə bilərsiniz. Bundan əlavə, təyinat yerində həmişə çəni doldura bilərsiniz, buna görə də geri dönüş səfəri barədə narahat olmağa ehtiyac yoxdur.