Mita-2

Son zamanlar, AlgoLand ölkəsinin kraliçası öz sarayı üçün pulların yuyulmasının yeni bir yolunu icad etmişdir. O qərara gəlib ki, bir şəhərdən digərinə səyahət etmək istəyən hər bir vətəndaş bu istəyi üçün öz vəsaiti ilə ödəniş etməlidir.

AlgoLandda $N$ şəhər var, şəhərlər $1$-dən $N$-ə kimi nömrələnib. Bəzi şəhərlər bir-birinə yollarla bağlıdır və bu yollar hər iki istiqamətdə hərəkət üçün açıqdır. Hər hansı bir yolda səyahətə başlayan, yolun sonuna qədər gedir.

Tutaq ki, indi ölkə sakini $A$ şəhərindən $B$ şəhərinə səyahət etmək istəyir. Kraliçanın yeni fərmanına görə bu səyahət zamanı ölkənin istənilən yolunda polis vətəndaşdan gömrük rüsumu ala (və ya almaya) bilər. Əgər vətəndaşın rüsumu ödəməyə kifayət qədər pulu yoxdursa, avtomatik həbsxanaya göndərilir. Fərmanda həmçinin ölkənin hər bir yolu üçün ödəniləcək rüsumun miqdarı müəyyən olunur. Kraliça ölkə əhalisinə qayğı göstərdiyindən, polisə bir səyahət zamanı vətəndaşdan ən çox iki dəfə rüsum almağa icazə verib.

Qeyd edək ki, $A$ şəhərindən $B$ şəhərinə getməyin bir neçə yolu varsa, vətəndaş onlardan istənilən birini özü seçə bilər.

Aşağıdakı proqramı tərtib edin:

\begin{itemize}\item giriş faylından ölkədəki şəhərləri və yolları, eləcə də səyahətin başlanğıc və son şəhərlərini oxuyur;\item vətəndaşın həbs olunmayacağına zəmanət vermək üçün özü ilə götürməli olduğu minimum pul miqdarını müəyyən edir;\end{itemize}

və nəticəni çıxış faylına yazır.