Harri Dələduz
Harri Xomyak böyük bir qəfəsdə yaşayır. Qəfəsin içində müxtəlif uzunluqlu bir istiqamətli borularla birləşdirilmiş n plastik top var. Harri hazırda s topundadır, yatağı isə t topundadır.
Sadə bir xomyak olaraq, Harri'nin beyninin yarıları bir-biri ilə o qədər də yaxşı ünsiyyət qura bilmir və hər biri özünəməxsus düşüncəyə sahibdir. Harri'nin sol beyin yarısı adətən çarxda aktiv olur və mümkün qədər uzun qaçmağı sevir. Sağ beyin yarısı isə nadir hallarda aktiv olur və mümkün qədər tez yatmaq istəyir. Birlikdə, Harri'nin beyin yarıları onu boru labirintindən keçirəcək və hər topda hansı çıxış borusunu izləyəcəyinə qərar verəcək.
Harri'nin beyin yarıları qərar verdikdən sonra çox yorulurlar və bir az dincəlməlidirlər, buna görə də ardıcıl iki qərar qəbul edə bilməzlər. Beləliklə, hansı borudan istifadə edəcəyinə dair qərarı növbə ilə qəbul edirlər, sol beyin yarısı birinci gedir. Beləliklə, s topundan başlayaraq, Harri'nin sol beyin yarısı hansı borunu izləyəcəyinə qərar verəcək, bəzi u topunda sol beyin yarısı dincələcək və sağ beyin yarısı çıxış borusunu seçəcək və s.
Beyin yarıları bütün xomyak qəfəsi ilə tanışdır və istənilən qədər uzağa plan qura bilərlər. Hər iki beyin yarısının optimal qərarlar qəbul etdiyini fərz etsək, Harri'nin yatağına çatması nə qədər vaxt alacaq? Hər topda ən azı bir çıxış borusu var, Harri'nin yatağının olduğu top istisna olmaqla (orada Harri asanlıqla sakitləşəcək). Heç bir boru topu özünə bağlamır, lakin bir topdan digərinə gedən bir neçə boru ola bilər.
Giriş məlumatları
Birinci sətir dörd tam ədəd ehtiva edir: plastik topların sayı n (1 ≤ n ≤ 10^5), boruların sayı m (0 ≤ m ≤ 2 * 10^5), Harri'nin və onun yatağının yeri s, t (0 ≤ s, t < n).
Sonra m sətir gəlir, hər biri bir borunu təsvir edən üç tam ədəd ehtiva edir: başlanğıc top a[i] (0 ≤ a[i] < n), son top b[i] (0 ≤ b[i] < n) və keçid vaxtı w[i] (1 ≤ w[i] ≤ 10^4). Qeyd edək ki, hər boru yalnız bir istiqamətdə hərəkət edə bilər.
Çıxış məlumatları
Harri'nin yatağına çatması üçün lazım olan vaxtı və ya Harri'nin borularda əbədi dolaşmağa məhkum olduğunu göstərən infinity sözünü çıxarın.