Мита-1

Son zamanlar, AlgoLand kraliçası saray üçün yeni pul toplama üsulu icad edib. O qərara alıb ki, bir şəhərdən digər şəhərə getmək istəyən hər bir vətəndaş bu səfərin haqqını öz vəsaiti hesabına ödəməlidir.

AlgoLand-da $n$ şəhər var, şəhərlər $1$-dən $n$-ə qədər nömrələnib. Bəzi şəhərlər yollarla bir-birinə birləşdirilib, hər yol hər iki istiqamətdə keçilə bilər. Səyyah bir yola daxil olduqda, mütləq onun sonuna qədər getməlidir.

Tutaq ki, bir sakin şəhər $A$-dan şəhər $B$-yə səyahət etmək istəyir. Kraliçanın yeni fərmanına əsasən, səyahət zamanı istifadə olunan istənilən yol üzrə polis bu vətəndaşdan məhkəmə rüsumu ala (və ya almaya) bilər. Əgər vətəndaşın bu haqqı ödəməyə kifayət qədər pulu olmasa, avtomatik olaraq həbsxanaya göndərilir. Fərmanda həmçinin hər yol üçün rüsumun məbləği də müəyyən edilib. Kraliça öz vətəndaşları haqqında düşündüyü üçün, polisə bir səyahət zamanı bir vətəndaşdan eyni yol üçün dəfələrlə rüsum almağı qadağan edib.

Qeyd edək ki, $A$-dan $B$-yə bir neçə müxtəlif yolla getmək olarsa, vətəndaş istənilən marşrutu seçə bilər.

Proqram tərtib edin, hansı ki:

• şəhərlərin və yolların təsvirini, həmçinin səfərin başlanğıc və son şəhərlərinin nömrələrini oxuyur;

• vətəndaşın həbsxanaya göndərilməməsi üçün mütləq özü ilə götürməli olduğu minimum pul məbləğini müəyyənləşdirir;

• nəticəni ekrana çıxarır.