Алекс восстанавливает сеть из n исследовательских станций. Некоторые пары уже соединены работающими двусторонними кабелями. По цепочке кабелей можно передавать сообщения через промежуточные станции.
Новый кабель можно проложить между любой парой различных станций u и v. Это стоит cᵤ + cᵥ монет. Если к станции подводят несколько новых кабелей, её стоимость оплачивается за каждый из них. Работающие кабели бесплатны и сохраняются.
Найдите минимальную общую стоимость новых кабелей, после добавления которых сообщение со станции 1 сможет дойти до любой станции.
Входные данные
Первая строка содержит целые числа n и m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000). Вторая строка содержит n целых чисел cᵢ (1 ≤ cᵢ ≤ 109).
Следующие m строк содержат номера концов работающего кабеля u и v (1 ≤ u, v ≤ n, u ≠ v). Между одной парой станций не более одного работающего кабеля.
Выходные данные
Выведите минимальную общую стоимость. Если сеть уже связна, выведите 0.
Пояснения к примерам
Пример 1. Минимальные стоимости в трёх компонентах равны 2, 4 и 9. Добавим кабели 2–5 и 2–6: (2 + 4) + (2 + 9) = 17.
Пример 2. Станции уже связаны.
| № | Входные данные | Выходные данные |
|
1
|
6 3
8 2 7 5 4 9
1 2
2 3
4 5
|
17
|
|
2
|
2 1
100 200
1 2
|
0
|