Səyahətlər
Армия Rzeczpospolita şəhəri Kostroma-dan Domnino kəndinə doğru irəliləyir. İki hetman, Stefan və Konstantin, ordunu idarə edirlər.
Stefan, Kostroma bölgəsinin xəritəsini əldə edib və hər gecə ordunu bir kənddən digərinə müəyyən bir yolla aparır. Konstantin isə kəndlər arasında gizli yolların xəritəsini əldə edib və hər gün ordunu bu yollardan biri ilə aparır. Hər iki hetman, hər yürüşdən əvvəl bələdçiləri İvan Susanindən hansı yolu seçməli olduqlarını soruşur.
Stefanın xəritəsində hər yolun uzunluğu göstərilib. Buna görə də, Stefan öz xəritəsinə əsasən hər kənd ilə Domnino kəndi arasındakı minimal məsafəni bilir. Eyni şəkildə, Konstantin də öz xəritəsinə əsasən hər kənd ilə Domnino arasındakı ən qısa məsafəni bilir.
İvan Susanin, gizli agent olaraq, özünü ifşa etmək istəmir. Buna görə də, hər dəfə yolu (Stefan üçün) və cığırı (Konstantin üçün) elə seçir ki, hetmanın sualına görə Domnino kəndinə olan ən qısa məsafə ciddi şəkildə azalsın.
İvana Domnino kəndinə qədər olan ən uzun mümkün yolu tapmağa kömək edin.
Giriş məlumatları
Birinci sətir üç tam ədəd n, s və t - Kostroma bölgəsindəki kəndlərin sayı, həmçinin başlanğıc kəndin və Domnino kəndinin nömrələrini ehtiva edir (2 ≤ n ≤ 1000, 1 ≤ s, t ≤ n). Kəndlər 1-dən n-ə qədər nömrələnib. Başlanğıc kənd və Domnino kəndi eyni deyil.
Sonra iki blok gəlir. Birinci Stefanın xəritəsini, ikinci isə Konstantinin xəritəsini müəyyən edir.
Hər blokun birinci sətiri kəndlər arasında yolların/cığırların sayını göstərən tam ədəd m-i ehtiva edir (n - 1 ≤ m ≤ 100000). Sonrakı m sətirin hər biri üç tam ədəd a, b və l-i ehtiva edir - onlar kəndlər a və b arasında uzunluğu l olan yolu/cığırı təsvir edir (1 ≤ a, b ≤ n; 1 ≤ l ≤ 10^6).
Rzeczpospolita ordusu yolla və ya cığırla hər iki istiqamətdə hərəkət edə bilər. Hər bir hetmanın öz xəritəsinə görə hər hansı kənddən hər hansı birinə keçə biləcəyi məlumdur. Ordu axşam təyin olunmuş başlanğıc kənddən başlayır və hər gecə bir yolla və hər gün bir cığırla hərəkət edir.
Çıxış məlumatları
İvan Susaninin Rzeczpospolita ordusunu Domnino kəndinə çatana qədər (yollar və cığırlar üzrə) apara biləcəyi ən uzun yolun uzunluğunu çıxarın. Əgər İvan Susanin ordunu sonsuz müddətə Domnino kəndinə çatmadan apara bilsə, onda "-1" rəqəmini çıxarın.