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

Автор:Евгений Татаринов, Денис Лысенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:128 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

В следующих K строках вводятся числа Ai, Bi и Ti.

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

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

Ограничения

1 ≤ N, K ≤ 104

1 ≤ Ai, Bi ≤ N

1 ≤ Ti ≤ 105

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

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

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

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

Подзадача Баллы Дополнительные ограничения
nk
1101 ≤ n ≤ 101 ≤ k ≤ 10
2201 ≤ n ≤ 1021 ≤ k ≤ 102
2301 ≤ n ≤ 1031 ≤ k ≤ 103
4401 ≤ n ≤ 1041 ≤ k ≤ 104

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

Стандартный вход Стандартный выход
1
4 4 
1 3 1 
3 2 8 
2 4 2 
4 1 4
11

0.062s 0.011s 13