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

В горах Тянь-Шаня раскинулись N горных аулов, соединённых M тропами. Каждая тропа двусторонняя — идёт между двумя аулами и имеет длину в километрах.

Чабан Эркин пасёт овец возле аула №1, а его невеста Айгуль живёт в ауле №N. Эркин решил пойти к ней в гости — самой короткой дорогой. Помогите ему: посчитайте длину кратчайшего пути из аула 1 в аул N.

Между двумя аулами может быть несколько разных троп. Тропа из аула в самого себя тоже допустима.

Если нет ни одной последовательности троп, ведущей из 1 в N, выведите -1.

Входные данные

• Первая строка: два числа N и M (2 ≤ N ≤ 10⁵, 0 ≤ M ≤ 2·10⁵).
• Далее M строк: три целых числа u v w — тропа между аулами u и v длины w (1 ≤ u, v ≤ N, 1 ≤ w ≤ 10⁴).

Выходные данные

Одно число: длина кратчайшего пути от аула 1 до аула N. Если пути нет — -1.

Пример 1

Вход:

5 6
1 2 4
1 3 2
2 3 1
2 4 5
3 4 8
4 5 3

Выход:

11

Пример 2

Вход:

3 1
1 2 5

Выход:

-1

Пояснение

В первом примере оптимальный путь: 1 → 3 (2 км) → 2 (1 км) → 4 (5 км) → 5 (3 км), итого 11 км. Во втором — нет тропы, ведущей в аул 3.

Подсказка по алгоритму: алгоритм Дейкстры с приоритетной очередью.