Нова пошта#7378
«Нова пошта» — служба швидкої доставки товарів та вантажів. Простір діяльності «Нової пошти» складається з складів, що з'єднані між собою вже відкритими і ліцензованими маршрутами. До кожного маршруту належить тільки два склади, розміщені на його кінцях.
Для повноцінної роботи компанії необхідно відкрити ще декілька маршрутів, щоб мати можливість виконувати доставку між будь-якими двома складами безпосередньо або через проміжні склади. Вартість ліцензії в кожному з складів записана в масиві . Для відкриття нового маршруту між складами і потрібно купити ліцензію на кожному складі, тобто витратити суму C_i + C_j.
Якої мінімальної суми достатньо, щоб забезпечити повноцінне функціонування служби доставки «Нова пошта»?
В першому рядку знаходяться числа і , 0 \leq N \leq 1000, у другому елементів масиву , 0 \leq C_i \leq 1000000. У наступних рядках записані пари чисел, що описують вже відкриті маршрути. Всі числові значення натуральні.
Відповідь до задачі.
Приклад 1