Məktəbə gedən yol#5486
Neftçilərin şəhəri bəzi cütləri küçələrlə birləşdirilmiş N nömrəli meydanlardan ibarətdir. Heç bir küçə meydanı özü ilə birləşdirmir və hər küçədən iki istiqamətdə hərəkət etmək olar. Hər cüt meydan arasında ən çox bir küçə vardır.
Tarixi səbəblərə görə, şəhərin bütün sakinlərinin evləri və şəhər təşkilatları yalnız meydanlarda yerləşir. Məktəb isə xüsusi olaraq 1-ci meydanda yerləşir. Şəhər adətinə əsasən, bir çox şagird məktəbə birlikdə getməyə çalışır. Bir sinifdən olan K oğlan bu adəti dəyişməməyə qərar verdilər. Lakin onlar fərqli meydanlarda yaşadıqları üçün bir hissəsini ayrıca getməli olurlar. Üstəlik, iqlim şəraiti səbəbindən hər biri evdən məktəbə ən qısa yolla gedir.
Tapşırığınız oğlanların birlikdə gedə biləcəyi ən uzun məsafəni müəyyənləşdirən proqram yazmaqdır.
Girişin birinci sətrində üç tam ədəd: N, M və K (1 \leq N \leq 1000, 1 \leq M \leq 10000, 1 \leq K \leq 100) verilir. Burada, N şəhərdəki meydanların sayı, M yolların sayı və K sinif yoldaşlarının sayıdır. İkinci sətrdə K təbii ədəd — 1 ilə N arasında olan və sinif yoldaşlarının evlərinin yerləşdiyi meydanların nömrələri verilir. Sonra M sətrdə yollar təsvir olunur. Hər yol üç ədəd ilə təyin olunur — birləşdirilən meydanların nömrələri və uzunluq. Uzunluq təbii ədəddir və 1000-i keçmir. Sətirdəki bütün ədədlər boşluqlarla ayrılıb. Hər K şagird məktəbə gedə biləcəkdir.
Çıxışa, sinif yoldaşlarının evlərindən məktəbə gedərkən birlikdə gedə biləcəkləri ən uzun məsafəni çıxarmaq lazımdır.
Nümunə 1