Avtobuslar və təyyarələr#668
Nəverləndiyada şə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 marşrut (avtobus və ya hava yolu) iki şəhəri hər iki istiqamətdə birləşdirir. İstənilən iki şəhər arasında hər növ marşrutdan ən çox bir dənə mövcuddur. Hər bir marşrutun müddəti məlumdur və hər iki istiqamətdə eynidir.
Marşrutların cədvəlləri vaxt baxımından tam şəkildə uyğunlaşdırılıb, belə ki, istənilən mürəkkəb marşrut (bir neçə hissədən ibarət olan) üzrə sərf olunan ümumi vaxt sadəcə həmin marşruta daxil olan ayrı-ayrı marşrutların müddətlərinin cəminə bərabərdir.
Başlanğıcda siz şəhərində yerləşirsiniz. Məqsədiniz mümkün qədər tez şəhərinə çatmaqdır. Təəssüf ki, maliyyə baxımından məhdudiyyətlisiniz və ən çox təyyarə bileti ala bilərsiniz (yəni ən çox dəfə aviareyslərdən istifadə edə bilərsiniz).
Birinci sətir boşluqlarla ayrılmış , , , ədədlərini ehtiva edir ( və başlanğıc və son şəhərlərin nömrələridir) (1 \leq N \leq 1000, 0 \leq M \leq 10, 1 \leq A \leq N, 1 \leq B \leq N, A \neq B).
İkinci sətir – avtobus marşrutlarının sayını ehtiva edir (1 \leq V \leq 20000). Növbəti sətirin hər biri bir marşrutun təsvirini aşağıdakı formada ehtiva edir:
(boşluqla ayrılmış), burada və bu marşrutla birləşdirilən şəhərlərin nömrələridir, isə onun müddətidir (saatlarla) (1 \leq I \leq N, 1 \leq J \leq N, I \neq J, 1 \leq K \leq 1000).
Növbəti sətir – aviareyslərin sayını ehtiva edir (1 \leq W \leq 20000). Növbəti sətirin hər biri bir aviareysin təsvirini ehtiva edir (avtobus marşrutları üçün olduğu kimi).
Ən qısa marşrutun müddətini (saatlarla) və ya , əgər şəhərinə çatmaq mümkün deyilsə, çap edin.
Nümunə 1