7255번 - Sujungimas 서브태스크다국어

Bitlandijoje pertvarkoma traukinių infrastruktūra. Šis darbas paskirtas Bitlandijos Traukinių Kompanijos vadovui Martynui.

Pirmiausia Martynas įvertino į kiekvieną miestą i atvykstančių keleivių srautą S_i. Martynas tarp miestų projektuoja geležinkelio linijas, tokias kad:

• Iš kiekvieno Bitlandijos miesto geležinkeliu būtų galima nukeliauti į bet kurį kitą Bitlandijos miestą (nebūtinai tiesiogiai).
• Nutiesti vieną traukinių liniją tarp miestų i ir j kainuoja S_i × S_j biteurų – didesnis srautas reikalauja daugiau investicijų (didesnė stotis, didesnis parkingas ir t.t.).

Dalis geležinkelių Bitlandijoje jau nutiesti, bet sumažėjus biudžetui Martynas nori nutiesti trūkstamas linijas už kuo mažesnę kainą.

Nustatykite, už kokią mažiausią kainą galima nutiesti likusias geležinkelio linijas, taip kad būtų tenkinami Martyno iškelti reikalavimai.

Pirmoje eilutėje pateikiami tarpu atskirti skaičiai N ir M – Bitlandijos miestų bei jau nutiestų geležinkelio linijų skaičius.

Antroje eilutėje pateikiami N tarpais atskirti skaičiai S_i.

Tolimesnėse M eilučių pateikiama po du skaičius v_i ir u_i, reiškiančius, kad tarp miestų v_i ir u_i jau nutiesta tiesioginė geležinkelio linija.

Išveskite kiek mažiausiai biteurų kainuos likusių geležinkelio linijų nutiesimas.

• 1 ≤ N ≤ 100 000
• 0 ≤ M ≤ 100 000
• 1 ≤ S_i ≤ 100
• 1 ≤ v_i, u_i ≤ N
• Visos poros (v_i, u_i) skirtingos ir v_i ≠ u_i.