Самый быстрый маршрут: алгоритм Дейкстры

Дорожная сеть: n перекрёстков и m двусторонних дорог, у каждой время проезда w минут. Найдите минимальное время пути от перекрёстка 1 до перекрёстка n или -1, если доехать нельзя.

Ввод: в первой строке n и m (1 ≤ n ≤ 2500, 0 ≤ m ≤ 2500), далее m строк a b w (1 ≤ a, b ≤ n, 0 ≤ w ≤ 10⁹). Возможны петли и несколько дорог между одной парой.

Вывод: минимальное время (может не поместиться в 32 бита) или -1.

Пример 1

Ввод:

4 5
1 2 4
1 3 1
3 2 2
2 4 5
3 4 10

Вывод:

8

Пример 2

Ввод:

3 1
1 2 5

Вывод:

-1