Мита-1
Son zamanlar AlgoLand ölkəsinin kraliçası öz kral sarayı üçün yeni bir pul yığma üsulu icad edib. O qərara gəlib ki, ölkənin bir şəhərindən digərinə səyahət etmək istəyən hər bir sakin bu arzusu üçü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 yolla hərəkətə başlayan 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ı bildirir ki, bu səyahət zamanı ölkənin hər hansı bir yolu ilə keçərkən polis bu sakindən kral sarayının xeyrinə rüsum ala bilər (və ya ala bilməz). Ə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ı sakinlərdən rüsumu bir dəfədən çox almalarını qadağan edib.
Qeyd edək ki, əgər A şəhərindən B şəhərinə getməyin bir neçə yolu varsa, sakin öz istəyinə görə səyahət üçün istənilən yolu seçə bilər.
Proqram yazın ki:
ö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 daxil etsin;
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 çıxarsın.
Giriş məlumatları
Birinci sətir 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. 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ış üç ədəd x, y, z (1 ≤ x, y ≤ n; x ≠ y; 1 ≤ z ≤ 10^9) ehtiva edir ki, bu da x və y şəhərlərini birləşdirən yolun olduğunu və bu yolla keçmək üçün rüsumun z pul vahidi olduğunu göstərir. Sonuncu sətir A və B (1 ≤ A, B ≤ n; A ≠ B) ədədlərini ehtiva edir - səyahətin başlanğıc və son şəhərlərinin nömrələri. A-dan B-yə keçməyin ən azı bir yolu olduğuna zəmanət verilir.
Çıxış məlumatları
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 çıxarın.