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

Новая почта

Новая почта

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
prb7378

«Новая почта» — служба скорой доставки товаров и грузов. Простор деятельности «Новой почты» состоит из N складов, которые соединены между собой уже открытыми и лицензированными M маршрутами. Каждый маршрут соединяет только два склада, которые находятся на его концах.

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

Какой минимальной суммы достаточно, чтобы обеспечить полноценное функционирование службы доставки «Новая почта»?

Входные данные

В первой строке находятся числа N и M, 0N1000, во второй N элементов массива C[1..N], 0Ci1000000. В следующих M строках размещены пари чисел, которые описывают уже открытые маршрути. Все числовые значения натуральные.

Выходные данные

Ответ на задачу.

Пример

Входные данные #1
5 3
7 4 8 3 9
1 3
2 4
1 5
Выходные данные #1
10
Источник III етеп Всеукраинской олимпиады по информатике в Житомирской обл. 2014-2015 г