Avtobuslar və təyyarələr
Nəvərləndiyada N şəhər var və bu şəhərlər arasında avtobuslar fəaliyyət göstərir. Bundan əlavə, bəzi şəhərlər arasında hava əlaqəsi (aviareyslər) də mövcuddur.
Hər bir reys (istər avtobus, istərsə də avia) iki şəhəri (hər iki istiqamətdə) birləşdirir. İstənilən iki şəhər arasında hər növ reysdən ən çox bir dənə mövcuddur. Hər bir reysin müddəti məlumdur və hər iki istiqamətdə eynidir.
Reyslərin cədvəli vaxt baxımından mükəmməl uyğunlaşdırılıb, belə ki, istənilən mürəkkəb marşrutun (bir neçə reysdən ibarət olan) vaxt sərfiyyatı sadəcə həmin marşruta daxil olan ayrı-ayrı reyslərin müddətlərinin cəminə bərabərdir.
Başlanğıcda siz A şəhərində yerləşirsiniz. Sizin məqsədiniz mümkün qədər tez B şəhərinə çatmaqdır. Təəssüf ki, maliyyə baxımından məhdudiyyətlisiniz, buna görə də ən çox M təyyarə bileti ala bilərsiniz (yəni ən çox M dəfə aviareyslərdən istifadə edə bilərsiniz).
Giriş verilənləri
Birinci sətir boşluqlarla ayrılmış N, M, A, B ədədlərini ehtiva edir (A və B - müvafiq olaraq başlanğıc və son şəhərlərin nömrələri) (1 ≤ N ≤ 1000, 0 ≤ M ≤ 10, 1 ≤ A ≤ N, 1 ≤ B ≤ N, A ≠ B).
İkinci sətir V - avtobus reyslərinin sayını ehtiva edir (1 ≤ V ≤ 20000). Növbəti V sətirin hər biri bir reysin təsvirini aşağıdakı formada ehtiva edir:
I J K (bir boşluqla ayrılmış), burada I və J bu reyslə birləşdirilən şəhərlərin nömrələridir, K isə onun müddətidir (saatlarla) (1 ≤ I ≤ N, 1 ≤ J ≤ N, I ≠ J, 1 ≤ K ≤ 1000).
Növbəti sətir W - aviareyslərin sayını ehtiva edir (1 ≤ W ≤ 20000). Növbəti W sətirin hər biri bir aviareysin təsvirini ehtiva edir (avtobus reysləri üçün olduğu kimi).
Çıxış verilənləri
Ən qısa marşrutun müddətini (saatlarla) və ya 0, əgər B şəhərinə çatmaq mümkün deyilsə, tapın.