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


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

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

Между n городами m двусторонних дорог с длинами. Маршрут — последовательность дорог от города 1 до города n, города и дороги в нём могут повторяться. Найдите наименьшую длину маршрута, которая строго больше длины кратчайшего.

Ввод. В первой строке n и m (2 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2· 10⁵). Далее m строк a b w (1 ≤ w ≤ 10⁶).

Вывод. Одно число или -1, если такого маршрута нет (например, если города не связаны).

Пример 1

Ввод

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

Вывод

7

Комментарии

Еще нет ни одного комментария.