Второй по длине путь

Вам даны n городов и m двунаправленных дорог, соединяющих эти города. Каждая дорога имеет длину . Эмиль, любитель приключений, хочет добраться из города 1 в город n по этим дорогам, но с небольшим дополнением: он выбирает самый короткий маршрут среди всех путей, чья длина строго больше, чем у общего кратчайшего пути.

Другими словами, ваша задача — помочь Эмилю найти длину второго по длине кратчайшего пути из города 1 в город n.

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

В первой строке входных данных заданы два целых числа n и m, обозначающие количество городов и количество дорог соответственно.
В следующих m строках содержатся три целых числа , , и , указывающие на то, что между городами и проложена двунаправленная дорога длиной .

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

Выведите одно целое число — длину второго по длине кратчайшего пути из города 1 в город n.

Пример