Дороги Кыргызстана
Отправить решение
Решать в редакторе
Сложность:
44%
Очки:
100 (частичный балл)
Ограничение по времени:
2.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Дороги Кыргызстана
В стране n городов, пронумерованных от 1 до n, и m двусторонних дорог, у каждой есть длина в километрах. Между парой городов может быть несколько дорог, встречаются и петли. Найдите длину кратчайшего пути из города 1 (Бишкек) в город n (Ош) или выведите -1, если проехать нельзя.
Формат ввода
В первой строке записаны n и m (2 ≤ n ≤ 5 · 10⁴, 1 ≤ m ≤ 10⁵). В следующих m строках записаны aᵢ, bᵢ, cᵢ — концы дороги и её длина (1 ≤ cᵢ ≤ 10⁶).
Формат вывода
Выведите длину кратчайшего пути или -1.
Пример 1
Вход:
4 4
1 2 5
2 4 5
1 3 1
3 4 20
Выход:
10
Пример 2
Вход:
3 1
1 2 7
Выход:
-1
Комментарии