Xəzinə Dalğıcılığı#3783
Əfsanələr tez-tez böyük xəzinələrdən bəhs edir. Amma əslində o xəzinələrə rast gəlmək nadir hadisədir. Onların çoxu dənizdə itib, ya da dağların altında gizlədilib. Amma ən böyük idolunuzdan öyrəndiyiniz kimi, xəzinələr muzeydə olmalıdır. Və indi bunun üçün bir şansınız var.
Bir ekspedisiya zamanı böyük bir mağara şəbəkəsi tapdınız. Yerlilərdən olan bir şaman, əcdadlarının mağaralarda gizlətdiyi inanılmaz dəyərlərdən danışıb. O hətta sizə mağara şəbəkəsini və xəzinələrin yerlərini göstərən qədim bir xəritə də verib. Təəssüf ki, mağara tamamilə su ilə doludur. Bura gəlmək də çox vaxt apardığından, qısa bir dalış edib mağara şəbəkəsini araşdırmaq qərarına gəlirsiniz. Amma mağara girişinə qayıtdığınızda xəbər alırsınız ki... yaxınlıqda vulkan püskürüb. Demək olar ki, əminliklə söyləmək olar ki, lava mağara girişlərini örtəcək və xəzinələr əbədi olaraq itəcək.
Bu sizi təhlükəli vəziyyətə salır. Çox az vaxtınız qalıb və cəmi bir köhnə hava balonunuz var. Yəni hər şey sizdən asılıdır. Yalnız bir dəfə dalış edə bilərsiniz. Bəs hansı marşrutu seçmək olar? Mağara şəbəkəsi çox böyükdür və mümkün qədər çox xəzinə xilas etməlisiniz. Universitetdə kompüter elmləri ilə məşğul olduğunuz vaxtlar yadınıza düşür... Və qəfildən ağlınıza gəlir. Hələ də noutbukunuz yanınızdadır. Hər şeyi xilas etməyə necə nail ola biləcəyinizi hesablamaq üçün proqram yaza bilərsiniz.
Tutaq ki, mağara daxilində xəzinəni tapmaq, ya da götürmək, yaxud mağara keçmək üçün hava sərf olunmur.
Hər test toplusu bir neçə testdən ibarətdir. Faylın əvvəlində bir sətirdə testlərin sayı olan (0 < t \leq 2000) ədədi verilir. Hər test üçün əvvəlcə və ədədləri verilir, buradan mağara sayını, isə mağaraları birləşdirən tunellərin sayını göstərir (1 \leq n \leq 10000, 0 \leq m \leq 50000). Sonra sətirdə tunellərin təsviri verilir: hər sətirdə , , - burada , mağara nömrələri, isə həmin tuneldən keçmək üçün lazım olan hava miqdarıdır (0 \leq a, b < n, 0 \leq l \leq 500). Tunellərdən sonra bir sətirdə mağara sistemindəki idol sayı verilir (0 \leq i \leq 8). Bu sətri bir sətirdə tam ədəddən ibarət p_1, \ldots, p_i ardıcıllığı izləyir - idol olan mağaraların nömrələri (0 \leq p_1, \ldots, p_i < n). Sonda isə bir ədəd verilir - sizdə olan hava litri (0 \leq a \leq 1000000). Siz həmişə başlanğıcda (və sonda) nömrəli düyündə olacaqsınız.
Hər bir test üçün bir sətirdə ədədini çap edin, burada - dalğıcın toplaya biləcəyi maksimal idol sayıdır.
Nümunə 1