Task
Time limit: 1000 ms,
Memory limit: 256 Mb

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

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

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

Формат выходных данных
Если соединить защищенным каналом связи два дата-центра разных интернет-гигантов возможно, то выведите в выходной файл три числа: x, y и d, означающие, что между городами x и y возможно провести канал связи суммарной стоимостью d. В городе x должен находиться дата-центр «Laim.UR», в городе y — дата-центр «Xenda». Если существует несколько оптимальных ответов, выведите любой. Если провести искомый канал невозможно, выведите −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
4 2 1 0 0 2 1 3 3 2 4 2	-1

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