Berlandiyada qar

Berlandiyada qışlar qarlı keçir, və bu qış da istisna deyil. Hər qış ölkənin hökuməti yollardan qarın təmizlənməsi məsələsi ilə məşğul olur. Bu vəzifə paytaxt üçün xüsusilə çətindir.

Qəbul edək ki, Berlandiyanın paytaxtı $n$ kəsişmə və $m$ bir istiqamətli yoldan ibarətdir. Hər bir yol iki fərqli kəsişməni x_i, y_i birləşdirir və x_i-dən y_i-yə doğru yönəlib. $i$-ci yolda w_i ton qar var.

Yolların təmizlənməsi üçün hökumət "Snow White" adlı bir özəl şirkəti işə cəlb edib. Hər gün şirkət bir qar təmizləyici maşını göndərir. O, işə $A$ nömrəli kəsişmədən başlayır, bir neçə kəsişmədən keçir və $B$-də dayanır. Maşının marşrutu $A$ və $B$ daxil olmaqla, təkrarlanan yolları və kəsişmələri əhatə edə bilər.

Maşın bir gün ərzində $A$ kəsişməsindən $B$-yə gedir, sürücü əlbəttə ki, yol hərəkəti qaydalarını pozmur. Maşın hər dəfə üzərində qar olan yoldan keçdikdə oradakı qar miqdarı $1$ ton azalır. Paytaxt sakinləri hökuməti büdcə israfçılığında ittiham edə biləcəyi üçün, sürücüyə qar olmayan yoldan getmək qadağandır.

Bəzi paytaxt yolları tarixi əhəmiyyət daşıyır, çünki üzərində hökumət binaları yerləşir. "Snow White" şirkətinin işi bitəndə bu yolların tamamı qardan təmizlənmiş olmalıdır. Məlumdur ki, $A$ kəsişməsi şəhərin tarixi mərkəzidir və bu o deməkdir ki, bütün tarixi yollar piyada olaraq tarixi mərkəzdən yalnız tarixi yollardan istifadə etməklə əlçatandır. Unutmayın, piyada baxımından yollar iki istiqamətlidir.

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 mümkün qədər çox günə bölməkdə maraqlıdır.

Sizin tapşırığınız — iş günlərinin maksimal sayı üçün məhdudiyyətlərə (yol istiqamətləri, tarixi yolların təmizliyi və s.) uyğun olaraq $A$-dan $B$-yə gündəlik marşrutlar ardıcıllığını tapmaqdır.