Тропы Тянь-Шаня
Отправить решение
Решать в редакторе
Сложность:
35%
Очки:
100 (частичный балл)
Ограничение по времени:
3.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Между N пунктами проложены M троп. Каждая тропа соединяет два пункта, имеет положительную длину и допускает движение в обе стороны. Найдите минимальную суммарную длину пути из пункта 1 в пункт N. Некоторые пункты могут быть недостижимы; между одной парой пунктов может быть несколько троп. Тропы из пункта в него же также допустимы.
Входные данные
В первой строке даны N и M (2 ≤ N ≤ 100000, 0 ≤ M ≤ 200000). В каждой из следующих M строк даны u, v и w: номера концов тропы и её длина (1 ≤ u, v ≤ N, 1 ≤ w ≤ 10000).
Выходные данные
Выведите длину кратчайшего пути из 1 в N. Если такого пути нет, выведите -1.
Пример
Ввод
5 6
1 2 4
1 3 2
2 3 1
2 4 5
3 4 8
4 5 3
Вывод
11
Комментарии