G. Короткий путь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На мой взгляд, люди делятся на две категории: одни живут будущим, а другие — прошлым. Нужно ли объяснять, к какой из них относился я? Тайна, за которой я охотился половину своей жизни, наконец обретала очертания. Добрый Волшебник не знал, где прячется Дракон. Но он знал, что в некоторых городах королевства разбойничьи притоны контролируются людьми из банды Дракона. Про каждый город он дал мне достоверную информацию, контролирует ли Дракон этот город.

Я смотрел на карту Сказочного Королевства в попытках понять, куда мне идти теперь. Всего в Королевстве было n городов, соединённых m дорогами, причём длина j-й дороги была wj. Я решил, что Дракон заляжет в одном из двух контролируемых его бандой городов, кратчайший путь между которыми минимален. Во-первых, между ними идёт самый высокий трафик Синего Чая, а во-вторых, в случае опасности можно быстро перебраться из одного города в другой. Оставалось только найти такую пару городов.

Входные данные

В первой строке записаны два целых числа через пробел: n и m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105) — количество городов в Сказочном Королевстве и количество дорог между ними соответственно.

Во второй строке записаны n целых чисел через пробел. На i-й позиции записано число 1, если i-й город контролируется бандой Дракона, иначе там записано число 0.

Далее в m строках записаны по три целых числа через пробел: ai, bi, wi (1 ≤ ai < bi ≤ n, 1 ≤ wi ≤ 109) — номера городов, соединённых дорогой, а также длина этой дороги. Города нумеруются с единицы. Каждая пара городов представлена не более одного раза.

Выходные данные

В первой строке выведите единственное целое число — длину кратчайшего пути между городами, в одном из которых предположительно скрывается Дракон.

Во второй строке выведите два целых числа через пробел — номера этих городов.

Если возможно несколько вариантов правильного ответа, выведите любой из них. Если ни для какой пары городов, контролируемых людьми Дракона, не существует пути между этими городами, то в единственной строке выведите «No luck at all» без кавычек.

Примеры
Входные данные
4 4
1 0 0 1
1 2 1
1 3 2
2 4 3
3 4 1
Выходные данные
3
4 1
Входные данные
7 9
1 0 1 1 0 0 1
1 2 5
1 4 100
2 3 5
2 5 4
2 6 4
3 7 100
4 5 2
6 7 2
5 6 3
Выходные данные
7
4 7
Входные данные
2 1
0 0
1 2 1
Выходные данные
No luck at all