Задача J. Женя и двоечка ≡

Условие

Последняя учебная неделя перед Новогодними каникулами. В классе прошла очень сложная и решающая полугодовую оценку контрольная по информатике, по которой Женя получил оценку 2, потому что списывал. Теперь Женя очень грустный, ведь он не получит обещанный игровой компьютер для учебы в качестве подарка. Он хочет пойти домой самым длинным путем, чтобы погрустить.

Школа находится на остановке под номером 1, дом Жени — на остановке под номером N. Все остальные остановки нумеруются целыми числами от 2 до N − 1. Женя не очень хорошо знает город, поэтому умеет ходить только между какими-то парами остановок. Таких пар K штук. Женя от остановки под номером A_i до остановки под номером B_i будет идти T_i минут (но не факт, что Женя осмелится пойти по обратному пути, то есть не факт, что Женя может ходить от B_i до A_i). Кстати, Женя всегда может дойти от школы до дома, возможно через промежуточные остановки.

Если вдруг Женя придет на остановку, на которой он живет (неважно, случайно или специально), то его тут же забирает мама и ведет домой, чтобы проводить воспитательную беседу. Больше Женя никуда не пойдет.

Помогите Жене! Сообщите, сколько минут он сможет ходить по городу, прежде чем дойдет до дома!

Формат входных данных

В первой строке вводятся натуральные числа N и K

В следующих K строках вводятся числа A_i, B_i и T_i.

Формат выходных данных

Выведите число, которое показывает, сколько минут он сможет ходить по городу, прежде чем дойдет до дома. Если Женя может бесконечно долго гулять по городу, выведите  − 1.

Ограничения

1 ≤ N, K ≤ 10⁴

1 ≤ A_i, B_i ≤ N

1 ≤ T_i ≤ 10⁵

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

4 4 
1 3 1 
3 2 8 
2 4 2 
4 1 4

11