Портали#7034
Деякі планети галактики, куди нещодавно переїхав Петрик П'яточкін, сполучено порталами. Якщо планети A і B сполучено, це означає, що на кожній із планет стоїть спеціальний пристрій — портал — для телепортації між ними. Істота, що входить у портал на планеті A, миттєво опиняється на планеті B і навпаки.
Один і той самий портал не можна використовувати для телепортації на різні планети. Якщо між парою планет ще немає сполучення, їх можна сполучити, але лише побудувавши на кожній із них по новому порталу. Будівництво ж порталів вимагає чималих витрат і може коштувати по-різному на різних планетах.
Будемо казати, що між двома планетами існує шлях телепортації, якщо з однієї планети можна потрапити на іншу, телепортувавшись один або кілька разів (використовуючи проміжні планети). На жаль, поки що не між кожними двома планетами існує шлях телепортації.
Маючи схему наявного сполучення планет і знаючи вартість будівництва порталу на кожній планеті, визначте, яку найменшу суму грошей потрібно витратити, щоб забезпечити існування шляху телепортації між кожною парою планет галактики.
У першому рядку вказано два натуральних числа: кількість планет галактики n~(n \le 1000) та кількість пар планет, безпосередньо сполучених між собою порталами.
У другому рядку перераховані натуральних чисел p_1, p_2, ..., p_n — вартості будівництва нового порталу відповідно на першій, другій, ..., -й планеті. Жодна з вартостей не перевищує 10^6.
У кожному з наступних рядків записано по два натуральних числа a_i та b_i~(1 \le a_i < b_i \le n, 1 \le i \le m), які задають пару сполучених між собою планет. Кожну пару записано на вході лише один раз.
Виведіть найменшу суму грошей, яку потрібно витратити на будівництво на деяких планетах порталів, щоб між кожними двома планетами, між якими не було шляху телепортації, такий шлях було створено.
Приклад 1
Приклад 2