eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Нова пошта

Нова пошта

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

«Нова пошта» - служба швидкої доставки товарів та вантажів. Простір діяльності «Нової пошти» складається з N складів, що з’єднані між собою вже відкритими і ліцензованими M маршрутами. До кожного маршруту належить тільки два склади, розміщені на його кінцях.

Для повноцінної роботи компанії необхідно відкрити ще декілька маршрутів, щоб мати можливість виконувати доставку між будь-якими двома складами безпосередньо або через проміжні склади. Вартість ліцензії в кожному з N складів записана в масиві C[1..N]. Для відкриття нового маршруту між складами i і j потрібно купити ліцензію на кожному складі, тобто витратити суму C[i]+C[j].

Якої мінімальної суми достатньо, щоб забезпечити повноцінне функціювання служби доставки «Нова пошта»?

Вхідні дані

В першому рядку знаходяться числа N і M, 0 ≤ N ≤ 1000, у другому N елементів масиву C[1..N], 0 ≤ C_{i }≤ 1000000. У наступних M рядках записані пари чисел, що описують вже відкриті маршрути. Всі числові значення натуральні.

Вихідні дані

Відповідь до задачі.

Приклад

Вхідні дані #1
5 3
7 4 8 3 9
1 3
2 4
1 5
Вихідні дані #1
10
Джерело III етеп Всеукраїнської олімпіади з інформатики в Житомирській обл. 2014-2015 р