Berlandiyada qar
Berlandiyada qışlar qarlı keçir və bu il də istisna deyil. Hər qış ölkənin hökuməti yolların qardan təmizlənməsi məsələsini həll etməlidir. Bu məsələ paytaxt üçün xüsusilə çətindir.
Paytaxtı n kəsişmə və m birtərəfli yoldan ibarət bir qraf kimi təsəvvür etmək olar. Hər yol iki fərqli kəsişmə x_i və y_i arasında birləşdirir və x_i-dən y_i-yə doğru istiqamətlənir. i-ci yolda w_i ton qar var.
Yolların təmizlənməsi üçün hökumət "Snow White" adlı özəl şirkəti işə götürüb. Hər gün şirkət bir qar təmizləyən maşın göndərir. Bu maşın A nömrəli kəsişmədən işə başlayır, bir neçə kəsişmədən keçərək B-yə çatır və dayanır. Maşın eyni yolları və kəsişmələri, o cümlədən A və B-ni təkrar keçə bilər.
Maşın bir gün ərzində A kəsişməsindən B kəsişməsinə gedir və sürücü yol hərəkəti qaydalarını pozmur. Maşın qarlı yoldan keçdikcə yoldakı qar miqdarını 1 ton azaldır. Paytaxt sakinləri hökuməti büdcə israfında ittiham edə biləcəyi üçün sürücüyə qar olmayan yoldan maşını sürmək qadağandır.
Bəzi şəhər yolları tarixi əhəmiyyətə malikdir, çünki onların üzərində hökumət binaları yerləşir. Buna görə də "Snow White" şirkətinin işi bitdikdən sonra bu yollar qardan təmizlənməlidir. Məlumdur ki, A kəsişməsi paytaxtın tarixi mərkəzidir və bu mərkəzdən bütün tarixi yollara piyada çatmaq mümkündür. Piyada baxımından yollar ikitərəfli hesab olunur.
Hökumət şirkətə hər iş günü üçün ödəniş edir, buna görə də "Snow White" rəhbərliyi işi maksimum gün sayına qədər uzatmaqda maraqlıdır.
Sizin vəzifəniz A-dan B-yə olan marşrutlar ardıcıllığını tapmaqdır ki, bu məhdudiyyətlərə cavab versin: hərəkət istiqaməti məhdudiyyəti, tarixi əhəmiyyətli yolların təmizliyi, maksimum iş günlərinin sayı.
Giriş verilənləri
Birinci sətir n, m, A, B (2 ≤ n ≤ 100, 0 ≤ m ≤ 5000, 1 ≤ A, B ≤ n, A ≠ B) tam ədədlərini ehtiva edir, burada n — paytaxtdakı kəsişmələrin sayı, m — yolların sayı. Növbəti m sətir dörd ədəd x_i, y_i, w_i, t_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i, 0 ≤ w_i ≤ 100, 0 ≤ t_i ≤ 1) ehtiva edir, burada x_i, y_i — yolun ucları, w_i — üzərindəki qar miqdarı, t_i — yolun tipi (0 adi yol, 1 — tarixi yol deməkdir). Hər bir istiqamətdə kəsişmə cütü arasında ən çox bir yol ola bilər.
Çıxış verilənləri
p — maksimum iş günlərinin sayını çıxarın. Növbəti p sətir qar təmizləyən maşının gündəlik marşrutlarının təsvirini ehtiva etməlidir. Marşrutu A ilə başlayıb, B ilə bitən kəsişmə nömrələrinin siyahısı kimi çıxarın, aralarında boşluq qoyun. Əgər bir neçə həll yolu varsa, istənilənini çıxarın, əgər həll yolu yoxdursa, 0 çıxarın.