Второй по длине путь
Отправить решение
Решать в редакторе
Сложность:
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
Комментарии