İşıqları Möhtəşəm Edin
Bob Roberts, kiçik Bobby-nin atası (problem D), orta ölçülü bir şəhərin Nəqliyyat Komissiyasında çalışır. Bob şəhərdəki işıqforların monitorinqi və lazım gəldikdə təmir qruplarının göndərilməsindən məsuldur. Bobun çox boş vaxtı var, buna görə də o, şəhərin müxtəlif nöqtələri arasında ən sürətli yolu tapmağa çalışır. Bobun əlində şəhərin küçələrinin planı və bütün işıqforların yerləşməsi və dövriyyə vaxtları haqqında çoxlu məlumat var. Problemi sadələşdirmək üçün o, aşağıdakı fərziyyələri edir:
Bütün avtomobillər eyni maksimum sürətlə hərəkət edir və əgər qırmızı işıqda dayanırlarsa, sürətlənib maksimum sürətə çatmaq üçün 5 saniyə vaxt tələb olunur. (Yəni, Bob avtomobilin əslində 5 saniyə ərzində yerində dayandığını və sonra maksimum sürətlə hərəkət etdiyini qəbul edir. Bob həmçinin işığın hərəkətə başlamaq üçün lazım olan 5 saniyə ərzində yenidən qırmızıya dönməyəcəyini qəbul edir.)
Hər bir avtomobil işıqfora tam sürətlə yaxınlaşır və əgər işıq yaşıl və ya sarıdırsa, işıqdan keçir, əgər qırmızı işıqdırsa, dərhal dayanır. Avtomobillər işıq yaşıl olmağa başladığı anda işıqdan keçməyə icazə verilir. Avtomobillər işıq qırmızıya dönməyə başladığı anda işıqda dayanmalıdır.
İşıqdan keçərkən dönmə vaxtı nəzərə alınmır. İki işıq arasında səyahət etmək mümkündür, lakin bəlkə də birbaşa deyil.
Bundan əlavə, geri dönmələrə icazə verilmir və marşrutlar kəsişməni yenidən ziyarət etməyəcək. Bu fərziyyələrə baxmayaraq, Bob minimum vaxt yollarını tapmaqda çətinlik çəkir. Gəlin ona kömək edə biləcəyinizi görək.
Giriş verilənləri
Hər bir test halının ilk sətri dörd müsbət tam ədəd n, m, s və e ehtiva edəcək, burada n (2 ≤ n ≤ 100) işıqforların sayıdır (nömrələnmiş 0-dan n - 1-ə qədər), m işıqforlar arasındakı yolların sayıdır və s və e (s ≠ e) arzu olunan səfərin başlanğıc və son işıqlarıdır. Sonra n sətir gələcək, hər biri g y r formasında olacaq, burada hər bir işığın yaşıl, sonra sarı, sonra qırmızı olduğu saniyələrin sayını göstərir. (1 ≤ g, y, r ≤ 100.) Bu sətirlərin birincisi işıq 0-a, ikincisi işıq 1-ə və s. aiddir. Bu n sətirdən sonra m sətir gələcək, hər biri bir yolu təsvir edir. Bu sətirlər l1 l2 t formasında olacaq, burada l1 və l2 yol ilə birləşdirilən iki işıqdır və t yolun uzunluğunu tam sürətlə keçmək üçün tələb olunan vaxtdır (saniyələrlə, t ≤ 500) — yolun başlanğıcında duraraq sürmək üçün bu dəyərə 5 əlavə etməlisiniz. Bütün yollar iki tərəflidir. Zaman 0-da, bütün işıqlar yaşıl dövrlərinə yeni başlayır və avtomobiliniz işıq s-də durur. Hərəkətə başlamaq üçün 5 saniyə tələb olunduğundan, g + y heç vaxt 5-dən az və ya bərabər olmadığını qəbul edə bilərsiniz. Son test halı 0 0 0 0 ehtiva edən bir sətir ilə bitir, bu da girişin sonunu göstərir.
Çıxış verilənləri
Hər bir test halı üçün başlanğıc işıqdan son işığa səyahət etmək üçün minimum vaxtı ehtiva edən bir sətir çıxarın. Nəticələrinizi mm:ss formasında çıxarın, səyahətin neçə dəqiqə və saniyə çəkdiyini göstərir. Əgər saniyələrin sayı 10-dan azdırsa, onun qarşısına 0 qoyun (yəni, 4:05 çıxarın, 4:5 deyil). Eyni şəkildə, əgər dəqiqələrin sayı 10-dan azdırsa, sadəcə bir rəqəm çap edin (məsələn, 4:05).