İnəklərin Marşrutlaşdırılması (Gümüş)

Fermasında qış soyuğundan bezmiş Bessi inək daha isti bir yerə istirahətə getməyi planlaşdırır. Təəssüf ki, o, yalnız Air Bovinia adlı bir aviaşirkətinin inəklərə bilet satmağa razı olduğunu öyrənir, bu biletlərin quruluşu isə xeyli mürəkkəbdir.

Air Bovinia $n$ təyyarəyə malikdir və hər biri iki və ya daha çox şəhərdən ibarət müəyyən bir «marşrut» üzrə uçur. Məsələn, təyyarələrdən biri $1$-ci şəhərdən başlayan, sonra $5$-ci şəhərdən, ardınca $2$-ci şəhərdən keçən və nəhayət $8$-ci şəhərə çatan marşrut üzrə uça bilər. Heç bir şəhər eyni marşrutda birdən çox dəfə rast gəlinmir.

Əgər Bessi hər hansı bir marşrutdan istifadə etməyi qərara alsa, o, həmin marşrutun istənilən şəhərində təyyarəyə minə bilər, sonra isə marşrut üzrə ondan sonra gələn istənilən şəhərdə düşə bilər. O, marşrutun birinci şəhərində minmək və ya sonuncu şəhərində düşmək məcburiyyətində deyil. Hər marşrutun sabit bir dəyəri var və Bessi bu marşrutun hər hansı hissəsindən istifadə etdikdə, keçdiyi şəhərlərin sayından asılı olmayaraq, bu dəyəri ödəməlidir.

Əgər Bessi səyahəti zamanı eyni marşrutdan bir neçə dəfə istifadə edərsə (yəni marşrutu tərk edib, sonra yenidən ona qayıdıb başqa bir şəhərdən başlayaraq təkrar istifadə edərsə), o, hər dəfə bu marşrutun dəyərini ödəməlidir.

Bessi $A$ şəhərində yerləşən fermasından $B$ şəhərində yerləşən tropik təyinat nöqtəsinə çatmağın ən ucuz yolunu tapmaq istəyir. Ona həm səyahətin minimal ümumi dəyərini, həm də bu minimal dəyərə malik bütün marşrutlar arasında onun etməli olduğu minimal sayda ayrı-ayrı uçuşları müəyyən etməkdə kömək edin.