Məktəbə gedən yol
Neftçilərin şəhəri, bəzi cütləri küçələrlə birləşdirilmiş N nömrəli meydanlardan ibarətdir. Hər küçənin uzunluğu məlumdur və öz-özünü birləşdirən küçələr yoxdur. Hər küçə iki istiqamətdə keçilə bilər və hər cüt meydan arasında yalnız bir küçə mövcuddur.
Tarixi səbəblərə görə, şəhərin bütün sakinlərinin evləri və müəssisələri yalnız meydanlarda yerləşir. Xüsusilə, məktəb 1 nömrəli meydanda yerləşir. Şəhərdə uzun müddətdir qəbul edilmiş ənənəyə görə, bir çox şagird məktəbə birlikdə getməyə çalışır. Bir sinifdən olan K oğlan bu ənənəni pozmamağa qərar verdilər, lakin onların evləri müxtəlif meydanlarda yerləşdiyinə görə, yolun bir hissəsini ayrı keçməli oldular. Üstəlik, iqlim şəraiti səbəbindən hər biri evdən məktəbə yalnız ən qısa yolla gedirdi.
Oğlanların birlikdə gedə biləcəyi ən uzun məsafəni hesablayan proqram yazmaq lazımdır.
Giriş verilənləri
Giriş faylının birinci sətirində üç tam ədəd var: N, M və K (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 1 ≤ K ≤ 100), burada N — şəhərdəki meydanların sayı, M — yolların sayı, K - sinif yoldaşlarının sayı. İkinci sətirdə K təbii ədəd var, 1 ilə N arasında olan və K sinif yoldaşlarının evlərinin yerləşdiyi meydanların nömrələrini müəyyən edir. Daha sonra M sətirdə yollar təsvir olunur. Hər bir yol üç ədəd ilə təyin olunur — birləşdirilən meydanların nömrələri və uzunluğu. Uzunluq 1000-i keçməyən təbii ədəddir. Sətirlərdəki bütün ədədlər boşluqlarla ayrılıb. İstənilən K şagirdin mövcud yollardan istifadə edərək evdən məktəbə gedə biləcəyi təmin edilir.
Çıxış verilənləri
Çıxış faylında sinif yoldaşlarının evlərindən məktəbə gedərkən birlikdə gedə biləcəyi ən uzun məsafəni yazmaq lazımdır.