e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

ADA Classes - Depth First Search

Портали

Деякі планети галактики, куди нещодавно переїхав Петрик П’яточкін, спо­лу­чено порталами. Якщо планети A і B сполучено, це означає, що на кожній із планет стоїть спеціальний пристрій - портал - для телепортації між ними. Істота, що входить у портал на планеті A, миттєво опиняється на планеті B і навпаки.

Один і той самий портал не можна використовувати для теле­пор­та­ції на різні планети. Якщо між парою планет ще немає сполучення, їх можна спо­лу­чити, але лише побудувавши на кожній із них по новому порталу. Будів­ниц­т­во ж порталів вимагає чималих витрат і може коштувати по-різному на різних планетах.

Будемо казати, що між двома планетами існує шлях телепортації, якщо з однієї планети можна потрапити на іншу, телепортувавшись один або кілька разів (використовуючи проміжні планети). На жаль, поки що не між кожними двома планетами існує шлях телепортації.

Маючи схему наявного сполучення планет і знаючи вартість будівництва порталу на кожній планеті, визначте, яку найменшу суму грошей потрібно витратити, щоб забезпечити існування шляху телепортації між кожною парою планет галактики.

Вхідні дані

У першому рядку вказано два натуральних числа: кількість планет галактики n (n1000) та кількість пар m планет, безпосередньо сполучених між собою порталами.

У другому рядку перераховані n натуральних чисел p1, p2, …, pn - вартості будівництва нового порталу відповідно на першій, другій, …, n-й планеті. Жодна з вартостей не перевищує 106.

У кожному з наступних m рядків записано по два натуральних числа ai та bi, 1ai < bin, 1im, які задають пару сполучених між собою планет. Кожну пару записано на вході лише один раз.

Вихідні дані

Вивести одне натуральне число - найменшу суму грошей, яку потрібно витратити на будівництво на деяких планетах порталів, щоб між кожними двома планетами, між якими не було шляху телепортації, такий шлях було створено.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 2
7 4 7 3
1 3
2 4
Вихідні дані #1
10

Пояснення: Можна сполучити четверту планету або з першою, або з третьою, задоволь¬нив¬ши умову задачі і витративши 3 + 7 = 10 грошових одиниць. Легко зрозуміти, що меншою кількістю витрачених грошей обійтися не вдасться.

Автор Данило Мисак
Джерело ІІІ (міський) етап Всеукраїнської учнівської олімпіади з інформатики, 2013, м. Київ