Мита-2
AlgoLand ölkəsinin kraliçası, krallıq sarayının gəlirlərini artırmaq üçün yeni bir pul yuma üsulu icad etdi. Bu üsula görə, ölkənin bir şəhərindən digərinə səyahət etmək istəyən hər bir sakin, bu səyahət üçün öz vəsaitindən istifadə etməlidir.
AlgoLandda N şəhər mövcuddur və bunlar 1-dən N-ə qədər nömrələnib. Bəzi şəhərlər iki istiqamətli yollarla bir-birinə bağlıdır. Hər hansı bir yola çıxan səyahətçi, həmin yolun sonuna qədər getməlidir.
Tutaq ki, ölkənin bir sakini A şəhərindən B şəhərinə getmək istəyir. Kraliçanın fərmanına əsasən, bu səyahət zamanı hər hansı bir yoldan keçərkən, polis həmin sakindən krallıq sarayına rüsum tələb edə bilər (və ya etməyə bilər). Əgər səyahətçi bu rüsumu ödəmək üçün kifayət qədər pulu yoxdursa, o, avtomatik olaraq həbsxanaya düşəcək. Fərman, həmçinin hər bir yol üçün rüsumun miqdarını müəyyən edir. Kraliça, sakinlərinin rifahını düşündüyü üçün, polislərə bir səyahət zamanı eyni sakindən iki dəfədən çox rüsum almağı qadağan edib.
Qeyd edək ki, əgər A şəhərindən B şəhərinə getməyin bir neçə yolu varsa, sakin istədiyi yolu seçə bilər.
Proqram yazın ki:
giriş faylından ölkənin şəhər və yollarının təsvirini, həmçinin səyahətin başlanğıc və son şəhərinin nömrələrini oxusun;
sakinin səyahət zamanı həbsxanaya düşməməsi üçün özü ilə götürməli olduğu minimum pul məbləğini müəyyən etsin;
və nəticəni çıxış faylına yazsın.
Giriş verilənləri
Giriş faylının ilk sətiri boşluqla ayrılmış N və M (2 ≤ N ≤ 10000, 1 ≤ M ≤ 100000) ədədlərini - şəhərlərin və yolların sayını ehtiva edir. Sonrakı M sətir yolları təsvir edir. Bu sətirlərin hər biri bir yolu təsvir edir və boşluqla ayrılmış üç ədəd X, Y, Z (1 ≤ X, Y ≤ N; X ≠ Y; 1 ≤ Z ≤ 1000000000) ehtiva edir ki, bu da X və Y şəhərlərini birləşdirən yolun olduğunu və bu yoldan keçmək üçün rüsumun Z pul vahidi olduğunu göstərir. Sonuncu sətir səyahətin başlanğıc və son şəhərlərinin nömrələri olan A və B (1 ≤ A, B ≤ N; A ≠ B) ədədlərini ehtiva edir. A şəhərindən B şəhərinə getməyin ən azı bir yolu olduğuna zəmanət verilir.
Çıxış verilənləri
Çıxış faylının yeganə sətiri, sakinin A şəhərindən B şəhərinə səyahət etmək və polislərin hərəkətlərindən asılı olmayaraq həbsxanaya düşməmək üçün özü ilə götürməli olduğu minimum pul məbləğinə bərabər olan bir ədəd ehtiva etməlidir.