Степан нещодавно був студентом, а вже декан. Зараз він навіть розклад складає для своєї улюбленої групи. Всім відомо, що після лекції студенти першим ділом біжать в буфет, для цього він хоче знайти таку лекційну аудиторію, з якої можна найшвидше добратись до буфету. На його факультеті аудиторій, між аудиторіями є швидкі доріжки, по яких можна швидко пересуватись від аудиторії до аудиторії в обох напрямках, рух по кожній з яких займає якусь кількість секунд. В деяких аудиторіях знаходяться буфети, деякі аудиторії — лекційні.
В першому рядку знаходяться два числа і (2 \leq N \leq 5000, 1 \leq M \leq 100000) — кількість аудиторій і кількість швидкісних доріжок відповідно.
В другому рядку знаходиться цілих чисел 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) з'єднані швидкісною доріжкою, час руху по якій дорівнює z_i секунд. Гарантується, що дві аудиторії не з'єднані більш ніж одною доріжкою.
Якщо існує такий шлях, по якому можна добратись з лекційної до буфету якнайшвидше, то виведіть три числа: x, y, d, які позначають, що з лекційної є шляхи до аудиторії з сумарним часом хвилин. Аудиторія має бути лекційною, в аудиторії має бути буфет. Якщо існує декілька відповідей, виведіть будь-яку з них. Якщо такого шляху не існує виведіть -1.
Приклад 1