Кратчайшая дорога
В стране N городов, пронумерованных от 1 до N, и M двусторонних дорог. Каждая дорога соединяет два города и имеет длину. Между двумя городами может быть несколько дорог.
Найдите длину кратчайшего пути из города 1 в город N.
Входные данные
В первой строке — два целых числа N и M (2 ≤ N ≤ 100 000, 1 ≤ M ≤ 200 000). Далее M строк, в каждой — три целых числа u, v, w: дорога между городами u и v (u ≠ v) длиной w (1 ≤ w ≤ 1 000 000 000).
Выходные данные
Одно целое число — длина кратчайшего пути из города 1 в город N. Если добраться невозможно, выведите -1.
Пример 1
Вход:
5 6
1 2 4
1 3 1
3 2 2
2 4 5
3 4 8
4 5 3
Выход:
11
Пример 2
Вход:
4 2
1 2 7
3 4 2
Выход:
-1
Пояснение
В первом примере кратчайший путь 1 → 3 → 2 → 4 → 5 имеет длину 1 + 2 + 5 + 3 = 11. Во втором примере города 1 и 4 не связаны. Длина пути может не поместиться в 32-битный тип. Используйте алгоритм Дейкстры с кучей (очередью с приоритетом).
Комментарии