Ən qısa yol
Hər axşam fermer Con böyük bir zəngi çalır ki, bu da inəklərini axşam yeməyi üçün tövləyə çağırır. İnəklər tövləyə mümkün qədər tez çatmaq üçün ən qısa yolu izləyirlər.
Fermada n sahədən ibarət bir dəst var, 1-dən n-ə qədər nömrələnmişdir və tövlə 1-ci sahədə yerləşir. Sahələr m ikitərəfli cığır dəsti ilə birləşdirilib. Hər cığırla keçid vaxtı əlaqələndirilir və hər hansı bir sahədən həmişə bəzi cığır dəstlərindən istifadə edərək tövləyə çatmaq mümkündür.
i sahəsi c[i] inək ehtiva edir. Yemək zəngini eşidən bu inəklərin hamısı tövləyə minimum vaxt sərf edən marşrutla gedir. Əgər minimum vaxtla bir neçə marşrut varsa, inəklər "leksikoqrafik" olaraq ən kiçik olanı seçirlər (yəni, onlar ilk növbədə daha aşağı indeksli sahəni istifadə edən marşruta üstünlük verirlər. Məsələn, 7, 3, 6, 1 sahələrini ziyarət edən yol, 7, 5, 1 sahələrini ziyarət edən yoldan üstün olacaq, əgər hər ikisinin keçid vaxtı eyni olarsa).
Fermer Con narahatdır ki, tövlə sahələrdən uzaqdır. O, hər bir inəyin səyahət vaxtını bütün inəklər üzrə toplayır və bu rəqəmi ümumi səyahət vaxtı adlandırır. O, bu rəqəmi mümkün qədər azaltmaq istəyir, tövlədən (sahə 1) öz seçiminə görə başqa bir sahəyə keçid vaxtı t olan bir əlavə "qısa" cığır əlavə edərək. Əgər inək adi yolunda qısa cığıra rast gəlsə, o, tövləyə daha tez çatdırarsa, onunla gedəcək. Əks halda, inək adi marşrutunu izləyəcək, hətta qısa cığırdan istifadə edərək səyahət vaxtını azalda bilsə belə.
Fermer Cona bir qısa cığır əlavə etməklə əldə edə biləcəyi ümumi səyahət vaxtının maksimum mümkün azaldılmasını müəyyən etməyə kömək edin.
Giriş Məlumatları
Birinci sətir n (1 ≤ n ≤ 10,000), m (n − 1 ≤ m ≤ 50000) və t (1 ≤ t ≤ 10000) ehtiva edir. Növbəti sətir n tam ədədi c[1] ... c[n] ehtiva edir, hər biri 0 ... 10000 aralığında yerləşir. Növbəti m sətirin hər biri üç tam ədəd a, b və t ilə cığırı təsvir edir (cığır a və b sahələrini t keçid vaxtı ilə birləşdirir). Keçid vaxtı 1-dən 25000-ə qədər olan aralıqdadır.
Çıxış Məlumatları
Fermer Conun əldə edə biləcəyi ümumi səyahət vaxtının maksimum mümkün azaldılmasını çıxarın.