Мита-3
Son zamanlar AlgoLand ölkəsinin kraliçası öz kral sarayı üçün pul yumağın yeni bir üsulunu icad etdi. O, qərara aldı ki, ölkənin bir şəhərindən digərinə səyahət etmək istəyən hər bir sakin bu istəyi üçün öz pulları ilə ödəməlidir.
AlgoLand ölkəsində N şəhər var, 1-dən N-ə qədər nömrələnmişdir. Bəzi şəhərlər hər iki istiqamətdə hərəkətə icazə verilən yollarla birləşdirilib. Hər hansı bir yola çıxan səyahətçi mütləq onun sonuna qədər getməlidir.
İndi fərz edək ki, ölkənin sakini A şəhərindən B şəhərinə səyahət etmək istəyir. Kraliçanın yeni fərmanı deyir ki, bu səyahət zamanı ölkənin hər hansı bir yolu ilə keçərkən, polislər bu sakindən kral sarayının xeyrinə rüsum ala bilərlər (və ya ala bilməzlər). Əgər bu zaman sakinin rüsumu ödəmək üçün kifayət qədər pulu yoxdursa, o, avtomatik olaraq həbsxanaya düşür. Fərman həmçinin ölkənin hər bir yolu üçün rüsumun miqdarını müəyyən edir. Kraliça öz ölkəsinin sakinlərinə qayğı göstərdiyi üçün polislərə bir səyahət zamanı sakindən üç 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ək üçün bir neçə yol varsa, sakin öz istəyi ilə səyahət üçün istənilən birini 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 şəhərlərin və yolların sayı olan N və M (2 ≤ N ≤ 10000, 1 ≤ M ≤ 100000) rəqəmlərini boşluqla ayıraraq ehtiva edir. Növbəti M sətir yolları təsvir edir. Bu sətirlərin hər biri bir yolu təsvir edir və boşluqla ayrılmış üç rəqəm 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) rəqəmlərini ehtiva edir. A-dan B-yə keçmək üçün ən azı bir yolun olduğu təmin edilir.
Çı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əğini göstərən bir rəqəm ehtiva etməlidir.