Тропы Тянь-Шаня


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

Сложность: 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

Комментарии

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