e-olymp
Соревнования

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, г. Киев