Второй по длине путь
Вам даны
n городов и m двунаправленных дорог, соединяющих эти города. Каждая дорога имеет длину . Эмиль, любитель приключений, хочет добраться из города 1 в город n по этим дорогам, но с небольшим дополнением: он выбирает самый короткий маршрут среди всех путей, чья длина строго больше, чем у общего кратчайшего пути.Другими словами, ваша задача — помочь Эмилю найти длину второго по длине кратчайшего пути из города
1 в город n.Входные данные
В первой строке входных данных заданы два целых числа
n и m, обозначающие количество городов и количество дорог соответственно.
В следующих m строках содержатся три целых числа , , и , указывающие на то, что между городами и проложена двунаправленная дорога длиной .Выходные данные
Выведите одно целое число — длину второго по длине кратчайшего пути из города
1 в город n.Пример
Вход | Выход |
6 7
1 2 3
2 3 4
3 6 5
2 6 9
1 4 3
4 5 8
5 6 2
| 13 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB