e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Нова пошта

Нова пошта

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

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

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

Вхідні дані:

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

Вихідні дані:

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

Time limit 1 second
Memory limit 64 MiB
Input example #1
5 3
7 4 8 3 9
1 3
2 4
1 5
Output example #1
10

Example description: Треба відкрити маршрут 1 4, витративши на ліцензування 7 + 3 = 10 грошових одиниць. Легко зрозуміти, що меншою кількістю витрачених грошей обійтися не вдасться.

Source III етеп Всеукраїнської олімпіади з інформатики в Житомирській обл. 2014-2015 р