Matrix
Bir neçə illik axtarışdan sonra Morpheus nəhayət The One - dostları arasında Neo kimi tanınan kompüter proqramçısı Thomas A. Andersonu tapdı. Siz və Neo ən yaxşı dostlarsınız. Əslində, bir neçə dəfə Regional Proqramlaşdırma Müsabiqələrində birlikdə iştirak etmisiniz. Morpheus sizə qırmızı həbi təklif edərək hər ikinizi Matrix dünyasından xilas etməyə qərar verdi. Morpheusun gəmisi Nebuchadnezzarda bir neçə aylıq təlimdən sonra Neo üçün Oracle ilə görüşmək vaxtı gəldi, Oracle The One-ın nəhayət ortaya çıxacağını proqnozlaşdırmışdı. Neo və Morpheus Matrix dünyasında onunla görüşməyə gedərkən siz hər şeyin plana uyğun getdiyinə əmin olmaq üçün real dünyada qaldınız.
Oracle ilə görüşdükdən sonra Neo və Morpheus Matrix dünyasındakı telefonlardan biri vasitəsilə real dünyaya qayıtmağa çalışırdılar. Morpheus qayıtdıqdan sonra və Neo telefonu istifadə etməzdən əvvəl bir agent onu məhv etdi və Neo Matrix dünyasında qaldı. Neo hələ tam potensialında olmadığı üçün onun yeganə seçimi agentlərlə döyüşməkdən qaçmaq və yolda agentlərlə qarşılaşma ehtimalı olmadan çata biləcəyi ən yaxın telefona qaçmaq idi.
Nebuchadnezzarda ən yaxşı proqramçı olduğunuz üçün Morpheus sizdən Neo-nun agentlə döyüşməli olub-olmayacağını müəyyən edən bir proqram yazmağı xahiş edir (agentlərin necə hərəkət edəcəyini bilmədiyiniz üçün kodunuz ən pis ssenarini nəzərə almalıdır). Əgər Neo agentlərdən qaça bilirsə, proqramınız Neo-nun agentlərin və telefonların yerləri və müxtəlif yerlər arasında hərəkət etmək üçün lazım olan vaxt nəzərə alınmaqla Matrix dünyasından nə vaxt çıxacağını müəyyən etməlidir.
Qeyd edək ki, əgər həm Neo, həm də agent eyni vaxtda telefon yerinə çatsalar, Neo telefonu götürməzdən əvvəl agentlə döyüşməli olacaq.
Giriş verilənləri
Girişin ilk sətri T (1 ≤ T ≤ 100) tam ədədini ehtiva edir - test hallarının sayı.
Hər bir test halı dörd tam ədəddən ibarət bir sətirlə başlayır: N (3 ≤ N ≤ 1000) - Matrix dünyasındakı yerlərin sayı, M - müxtəlif yerləri birləşdirən yolların sayı, NA - agentlərin sayı və NT - telefonların sayı. (NA, NT > 0, NA+NT < N-1)
Növbəti M sətir hər biri üç tam ədəd u, v və m (0 ≤ u, v < N, 1 ≤ m ≤ 30) ehtiva edir. İlk iki tam ədəd matriksdəki iki yeri (Neo-nun başlanğıc yeri 0 ilə) və üçüncü tam ədəd bu iki yer arasında hərəkət etmək üçün tələb olunan vaxtı (dəqiqələrlə) təmsil edir.
Növbəti sətir agentlərin yerlərini verən NA tam ədəd ehtiva edir.
Test halının son sətri telefonların yerlərini verən NT tam ədəd ehtiva edir.
Qeyd edək ki, 0 yerində (yəni Neo-nun başlanğıc yerində) nə agent, nə də telefon yoxdur. Həmçinin, əvvəlcə həm telefon, həm də agent olan yer yoxdur.
Çıxış verilənləri
Hər bir test halı üçün Neo-nun təhlükəsizliyini təmin edən heç bir yol yoxdursa, "Neo may fight an Agent" çap edin. Əks halda, Matrix dünyasından çıxmaq üçün lazım olan vaxtı (dəqiqələrlə) çap edin.