C. Алгоритм Дейкстры?
ограничение по времени на тест
1 second
ограничение по памяти на тест
64 megabytes
ввод
stdin
вывод
stdout

Задан неориентированный взвешенный граф, вершины которого пронумерованы от 1 до n. Ваша задача найти кратчайший путь из вершины 1 в вершину n.

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

В первой строке содержатся целые числа n и m (2 ≤ n ≤ 105, 0 ≤ m ≤ 105), где n — количество вершин, а m — количество ребер в графе. Далее в m строках содержатся сами ребра, по одному в строке. Каждое ребро задается тремя числами ai, bi, wi (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 106), где ai, bi — это концы ребра, а wi — его длина.

Граф может содержать кратные ребра и петли.

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

Выведите число -1 если пути нет или сам кратчайший путь, если он существует.

Примеры
Входные данные
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
Выходные данные
1 4 3 5
Входные данные
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
Выходные данные
1 4 3 5