İstila halında, zəhmət olmasa...#9886
Curiosity marsarabası Marsda təkcə su deyil, həm də aqressiv qanlı-canlı yadplanetlilər dəstəsi aşkar etdikdən sonra Luven-la-Nëv bələdiyyəsi ehtiyat tədbirləri görmək qərarına gəldi: yadplanetlilərin hücumu zamanı şəhərin bütün sakinlərini sığındıra biləcək sığınacaqlar tikildi.
Bütün şəhər boyunca yadplanetlilərdən qorunan bir neçə sığınacaq tikilib ki, şəhər sakinləri istila zamanı orada gizlənə bilsinlər. Lakin bələdiyyə qaydaları və yerli tikinti normaları səbəbindən sığınacaqların ölçüsü məhduddur. Buna görə hakimiyyət orqanları hər bir sakin üçün, bir gün NLO donanması günəşi örtsə, sakin rahatlıqla hansı sığınacağa yönələcəyini müəyyən etməlidir. Heç bir sığınacağa onun tutumundan artıq insan göndərilə bilməz, və bu şərtə riayət olunduğu halda bütün insanların sığınacaqlara çatması üçün lazım olan vaxtı minimuma endirmək vacibdir.
Luven-la-Nëv şəhərini yaşayış məntəqəsindən və onları birləşdirən ikitərəfli yoldan ibarət şəbəkə kimi təsəvvür edək. Sığınacaqlar şəhərin nöqtəsində yerləşir və hər birinin maksimum tutumu verilmişdir. Sakinləri sığınacaqlar arasında optimal şəkildə bölüşdürsək, bütün sakinlərin sığınacaqlara çatması üçün minimum vaxt nə qədər olacaq?
Luven-la-Nëv bələdiyyəsi sığınacaqların ümumi tutumunun bütün sakinlər üçün kifayət etməsinə və hər bir sığınacağa istənilən məntəqədən çatmaq mümkün olmasına diqqət yetirib. Beləliklə, hamını sığındırmaq həmişə mümkündür.
Birinci sətirdə üç tam ədəd verilir: məntəqələrin sayı n~(1 \le n \le 10^5), yolların sayı m~(0 \le m \le 2 \cdot 10^5) və sığınacaqların sayı s~(1 \le s \le 10).
İkinci sətirdə tam ədəd p_1, p_2, \dots, p_n~(0 \le p_i \le 10^9) verilir, burada p_i — məntəqəsində yaşayan insanların sayıdır.
Sonrakı sətirin hər birində üç tam ədəd , və w~(1 \le u, v \le n, 1 \le w \le 10^9) verilir. Bu o deməkdir ki, və məntəqələri keçilməsi vaxt tələb edən ikitərəfli yolla birləşdirilib. İstənilən iki məntəqə birbaşa ən çox bir yolla birləşdirilə bilər və heç bir yol məntəqəni özü ilə birləşdirmir.
Sonuncu sətirin hər birində iki tam ədəd s_i və c_i~(1 \le s_i \le n, 1 \le c_i \le 10^9) verilir. Bu o deməkdir ki, s_i məntəqəsində tutumu c_i olan sığınacaq yerləşir.
Bütün sakinləri sığındırmaq üçün tələb olunan minimum vaxtı çap edin.
Nümunə 1
Nümunə 2
Nümunə 3
Nümunə 4