Mita-3

Son zamanlar, AlgoLand kraliçası kral sarayı üçün pul yığmaq üçün yeni bir qayda icad edib. O qərara alıb ki, bir şəhərdən digərinə səyahət etmək istəyən hər bir sakin bu istəyi üçün öz pulu ilə ödəməlidir.

AlgoLandda $N$ şəhər var, 1-dən $N$-ə kimi nömrələnmişdir. Bəziləri ikitərəfli hərəkətə imkan verən yollarla birləşdirilib. Səyyah bir yola daxil olduqda, o yolun sonuna qədər getməlidir.

Tutaq ki, sakin şəhər $A$-dan şəhər $B$-yə getmək istəyir. Kraliçanın yeni fərmanına görə, bu səyahət zamanı səyyah hər hansı bir yol ilə hərəkət etdikdə, polis səyyahdan kral sarayı üçün gömrük haqqı ala bilər (və ya heç almaya da bilər). Əgər səyyah hər hansı haqqı ödəməyə kifayət qədər pulu yoxdursa, dərhal həbsxanaya göndərilir. Fərman həmçinin hər yol üçün konkret haqq məbləğini müəyyənləşdirir. Kraliça, sakinlərini qoruduğu üçün, polisin bir səyahət ərzində üç dəfədən çox gömrük haqqı almasını qadağan edib.

Qeyd edək ki, $A$-dan $B$-yə getməyin bir neçə yolu varsa, səyyah istənilən marşrutu sərbəst seçə bilər.

Proqram yazın ki:

• giriş faylından ölkənin şəhər və yollarının təsvirini, eləcə də səyahət üçün başlanğıc və son şəhərlərin nömrələrini oxusun;

• sakin həbsxanaya düşməməyə təmin etmək üçün mütləq özü ilə aparmalı olduğu minimum pul məbləğini müəyyən etsin;

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