Задан неориентированный взвешенный граф, вершины которого пронумерованы от 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
1000 ms 64 Mb Правила оформления программ и список ошибок при автоматической проверке задач