Cow Routing II

Öz təsərrüfatındakı soyuq qış havasından bezmiş Bessie inək istirahət üçün daha isti bir məkana uçmağı planlaşdırır. Təəssüf ki, o, yalnız bir aviaşirkətin, Air Bovinia-nın, inəklərə bilet satmağa razı olduğunu və bu biletlərin bir qədər mürəkkəb olduğunu aşkar edir.

Air Bovinia-nın $n$ təyyarəsi var, 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, bir təyyarə $1$ şəhərindən başlayan, sonra $5$ şəhərinə, daha sonra $2$ şəhərinə və nəhayət $8$ şəhərinə uçan bir marşrut üzrə uça bilər. Heç bir şəhər marşrutda birdən çox dəfə görünmür.

Bessie bir marşrutdan istifadə etməyi seçərsə, o, marşrut üzrə istənilən şəhərdə təyyarəyə minə bilər və sonra marşrutda daha sonra görünən istənilən şəhərdə düşə bilər. O, birinci şəhərdə minmək və ya son şəhərdə düşmək məcburiyyətində deyil. Hər marşrutun sabit bir dəyəri var, Bessie həmin marşrutun hər hansı bir hissəsindən istifadə edərsə, marşrut boyunca neçə şəhər ziyarət etməsindən asılı olmayaraq bu dəyəri ödəməlidir. Bundan əlavə, Bessie hər marşrutdan ən çox bir dəfə istifadə edə bilər (yəni, o, bir marşrutun bir hissəsindən istifadə edib sonra həmin marşrutun başqa bir hissəsindən istifadə edə bilməz).

Bessie, $A$ şəhərində yerləşən öz təsərrüfatından $B$ şəhərində yerləşən tropik məkanına getməyin ən ucuz yolunu tapmaq istəyir. Mürəkkəb bir marşrutla məşğul olmaq istəmədiyi üçün, o, ən çox iki marşrutdan istifadə etmək istəyir. Onun ödəməli olduğu minimum ümumi dəyəri tapmasına kömək edin.