Олимпиадный тренинг

Задача . Защищенное соединение


В свете недавних новостей о прослушке каналов связи, два непримиримых интернет-гиганта Урагании «Laim.UR» и «Xenda» решили подписать соглашение об установлении защищенного канала связи между дата-центрами друг друга. В Урагании n городов, но, к сожалению, ни в одном городе нет дата-центров обоих гигантов. Поэтому для формирования защищенного канала придется прокладывать междугородние линии связи.
Специалисты компаний определили m пар городов, которые можно соединить, проложив сегмент канала связи, и оценили стоимость создания такого сегмента для каждой из этих пар.

Результирующий канал может состоять из нескольких сегментов. Он должен начинаться в одном из городов, где находится дата-центр первой компании, может проходить через промежуточные города и должен заканчиваться в городе, где находится дата-центр второй компании.
Теперь необходимо определить минимальную стоимость защищенного канала, соединяющего два дата-центра компаний.

Входные данные:
В первой строке находятся целые числа n и m (2 ≤ n ≤ 5 000, 1 ≤ m ≤ 105 ) — количество городов и количество пар городов, которые можно соединить сегментом канала связи. Во второй строке находятся n целых чисел ai (0 ≤ ai ≤ 2). Если ai = 0, то в i-м городе нет дата-центра ни одного из гигантов. Если ai = 1, то в i-м городе есть дата-центр «Laim.UR», а если ai = 2, то в i-м городе находится дата-центр «Xenda». Гарантируется, что среди этих чисел есть как минимум одна единица и одна двойка. В каждой из следующих m строк находится по три целых числа — si , ti и ci , которые означают, что города si и ti (1 ≤ si , ti ≤ n, si != ti) можно соединить сегментом канала связи стоимостью ci (1 ≤ ci ≤ 105 ). Каждую пару городов можно соединить не более чем одним сегментом канала.

Выходные данные:
Если соединить защищенным каналом связи два дата-центра разных интернет-гигантов возможно, то выведите в выходной файл три числа: x, y и d, означающие, что между городами x и y возможно провести канал связи суммарной стоимостью d. В городе x должен находиться дата-центр «Laim.UR», в городе y — дата-центр «Xenda». Если существует несколько оптимальных ответов, выведите любой. Если провести искомый канал невозможно, выведите −1.

Примеры
Входные данные Выходные данные
1 6 7
1 0 1 2 2 0
1 3 3
1 2 4
2 3 3
2 4 2
1 6 5
3 5 6
5 6 1
3 4 5
2 4 2
1 0 0 2
1 3 3
2 4 2
-1

Пояснение
В первом примере оптимально построить канал связи из двух сегментов: 3 − 2 и 2 − 4.


time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w646
Комментарий учителя