Гра зi стiльцями#146

Гра зi стiльцями

1 секунда
512 мегабайтів
Середня

Вчитель з математики ЛІ є організатором розважальних конкурсів в ліцеї. Фінальним конкурсом буде відома всім "Гра зі стільцями". Її правила наступні: є декілька стільців, їх кількість повинна бути на один менше, ніж кількість учасників. Наприклад, якщо гравців сім — стільців шість. Коли звучить музика, всі бігають навколо стільців. Як тільки музика зупиниться, гравці швидко повинні сісти на стільці. Кому місця не дісталося той вибуває з гри. Потім один стілець забирається і гра продовжується поки не залишиться один учасник.

ЛІ знає, що нагорода за фінальний конкурс дуже цінна — книжки з математики. Звичайно, вона хоче, щоб їх отримав її найулюбленіший учень, Степан. Як організатор, ЛІ може казати коли зупиняти музику, тому вона хоче визначити такий момент, щоб Степан точно встиг зайняти стілець.

Більш формально, поле для гри можна уявляти як неорієнтований граф з вершин та ребер, кожне ребро якого має певну довжину. В деяких вершинах графу знаходяться стільці, деякі вершини представляють з себе місце, в якому може знаходитись якийсь учасник під час гри музики, інші вершини виступають в ролі проміжних, через які може лежати шляхи учасника до стільця.

ЛІ хоче знати найкоротший шлях від якоїсь вершини з учасником до якоїсь вершини зі стільцем. Таким чином, вона зупинить музику тоді, коли Степан буде знаходитись в цій вершині і він буде мати перевагу в тому, що найкоротший шлях до стільця в нього буде не більший, ніж в будь-якого з інших учасників.

Вхідні дані

В першому рядку знаходяться два числа і (2 \leq N \leq 70000, 1 \leq M \leq 200000) — кількість вершин і ребер, відповідно. В другому рядку знаходиться цілих чисел A_i (0 \leq A_i \leq 2). Якщо A_i = 0, то в цій вершині нема ні стільця, ні учасника. Якщо A_i = 1, то в цій вершині знаходиться учасник. Якщо A_i = 2, то в цій вершині знаходиться стілець.

Гарантується, що хоча б одне з цих чисел дорівнює одиниці, і хоча б одне дорівнює двійці.

В кожному з наступних рядків знаходиться по три числа X_i, Y_i, Z_i, які позначають, що між вершинами X_i і Y_i (1 \leq X_i; Y_i \leq N, X_i \neq Y_i, 0 \leq Z_i \leq 100000) з'єднані ребром, довжина якого дорівнює Z_i хвилин. Гарантується, що два ребра з'єднані не більш ніж одним ребром.

Вихідні дані

Якщо існує такий шлях, по якому Степан може добратись з початкового місця до стільця якнайшвидше, то виведіть три числа: x, y, d, які позначають, що з вершини є шлях до вершини з сумарним часом хвилин. Додатково мають виконуватись умови A_x = 1, A_y = 2.

Якщо такого шляху не існує виведіть -1.

Якщо існує декілька відповідей, виведіть будь-яку з них.

Приклади

Приклад 1

Loading
Loading