Дороги Кыргызстана


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

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

Комментарии

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