C. Оптимизация транспортной системы Марса.
Шёл 2058 год. Колонии первых поселенцев уже высадились на Марсе и стали его обживать, а Яндекс.Такси начала развертывание системы шатл-станций.
Для нормального функционирования шатл-станция нуждается в постоянном питании от энергетической сети. Чтобы запитать станцию нужно либо построить урановый ядерный генератор энергии внутри самой станции, либо проложить кабель до другой (уже запитанной) шатл-станции. Стоимость строительства генератора внутри разных шатл-станций может отличаться. Проведение кабеля между шатл-станциями также варьируется по стоимости и не всегда возможно. Кабельное соединение является двунаправленным.
Задача состоит в том, чтобы организовать эффективное (с минимальной стоимостью) питание всех шатл-станций.
На вход программа получает общее число шатл-станций, стоимости строительства генераторов для каждой шатл-станции и описания всех возможных кабелей между шатл-станциями (номера соединяемых станций и стоимость прокладки кабеля).
Формат ввода Первая строка содержит одно целое неотрицательное число шатл-станций N≤1000. Вторая строка содержит N чисел, задающих стоимости строительства генератора внутри соответствующей станции. Третья строка содержит одно целое неотрицательное число возможных кабелей K ≤100000 между шатл-станциями.
Последующие K строк (начиная с четвёртой) содержат описание одного кабеля - три целых неотрицательных числа: номер первой станции, номер второй станции и стоимость проведения. Формат вывода Одно целое число - минимальная стоимость питания всех шатл-станций для заднной конфигурации.
Пример 1
Ввод
1
77
0
Вывод
77
Пример 2
Ввод
2
11 29
1
1 2 17
Вывод
28
Примечания
Станции нумеруются с единицы.
Числа внутри строки разделяются одним пробелом.
Корректность входных данных проверять не требуется.