Portallar

Bəzi planetlər, Petya Pyatoçkinin yeni köçdüyü qalaktikada portallarla birləşdirilib. Əgər A və B planetləri birləşdirilibsə, bu o deməkdir ki, hər iki planetdə xüsusi bir cihaz — portal — var və bu cihazlar onların arasında teleportasiya üçün istifadə olunur. A planetindəki portala daxil olan bir varlıq dərhal B planetinə və əksinə keçə bilər.

Eyni portal fərqli planetlərə teleportasiya üçün istifadə edilə bilməz. Əgər planetlər arasında hələ bir birləşmə yoxdursa, onları birləşdirmək mümkündür, lakin bunun üçün hər birində yeni portal tikilməlidir. Portal tikintisi böyük xərclər tələb edir və müxtəlif planetlərdə fərqli qiymətə başa gələ bilər.

İki planet arasında teleportasiya yolu olduğunu deyəcəyik, əgər bir planetdən digərinə bir və ya bir neçə dəfə teleportasiya edərək (aralıq planetlərdən istifadə etməklə) keçmək mümkündürsə. Təəssüf ki, hələlik hər iki planet arasında teleportasiya yolu yoxdur.

Planetlərin mövcud birləşmə sxemini və hər planetdə portal tikintisinin dəyərini bilə-bilə, qalaktikadakı hər bir planet cütü arasında teleportasiya yolunun mövcudluğunu təmin etmək üçün ən azı nə qədər pul xərcləmək lazım olduğunu müəyyən edin.

Giriş verilənləri

Birinci sətirdə qalaktikadakı planetlərin sayı $n(n\le 1000)$ və portallarla birbaşa birləşdirilmiş planet cütlərinin sayı $m$ göstərilib.

İkinci sətirdə $n$ təbii ədədlər $p_1,p_2,...,p_n$ — müvafiq olaraq birinci, ikinci, ..., $n$-ci planetdə yeni portal tikintisinin dəyəri verilmişdir. Heç bir dəyər $10^6$-dan çox deyil.

Növbəti $m$ sətirdə hər biri iki təbii ədəd $a_i$ və $b_i(1\le a_i<b_i\le n,1\le i\le m)$ yazılıb ki, bir-biri ilə birləşdirilmiş planet cütünü göstərir. Hər bir cüt girişdə yalnız bir dəfə yazılıb.

Çıxış verilənləri

Bir təbii ədəd çıxarın — bəzi planetlərdə portalların tikintisinə xərclənəcək ən az məbləği, belə ki, teleportasiya yolu olmayan hər iki planet arasında belə bir yol yaradılsın.

Nümunələr