Ağır yük#4114
Johnson Böyük Yük Maşınları İnk. - böyük yük maşınlarının istehsalı üzrə ixtisaslaşmış bir şirkətdir. Onların son modeli Godzilla V12 o qədər böyükdür ki, yük maşınının daşıya biləcəyi yük miqdarı məhdud deyil. Yalnız yolların çəkə biləcəyi çəki məhdudiyyətləri mövcuddur.
Başlanğıc və son şəhəri bilmək şərti ilə, sizdən iki verilmiş şəhər arasında hələ də mövcud olan bir yol üçün Godzilla V12-nin maksimum yüklənməsini müəyyən etmək tələb olunur.
Bir və ya bir neçə testdən ibarətdir. Hər testin ilk sətiri iki ədəd ehtiva edir: şəhərlərin sayı n (2 ≤ n ≤ 200) və yolların sayı r (1 ≤ r ≤ 19900), bu da ölkənin yol şəbəkəsini təşkil edir.
Daha sonra r sətir gəlir, hər biri iki şəhəri birləşdirən bir yolu təsvir edir, şəhərlərin adları və bu yolla daşınmasına icazə verilən maksimum çəki. Şəhər adları 30 simvoldan çox deyil və boşluq ehtiva etmir. Çəki məhdudiyyətləri 0 - 10000 aralığında yerləşir. Bütün yollar iki tərəflidir.
Hər testin son sətiri iki şəhərin adını ehtiva edir: başlanğıc və son şəhər. Son sətir n və r üçün iki sıfır ehtiva edir.
Hər test üçün üç sətir çıxarın:
"Scenario #x" mesajı olan bir sətir, burada x testin nömrəsidir
"y tons" mesajı olan bir sətir, burada y yük maşınının maksimum yüklənmə miqdarıdır
Əgər daha bir test gəlirsə, boş bir sətir
Nümunə 1