01. Дейкстра?#

📝 Условие#

Дан взвешенный неориентированный граф. Найдите кратчайший путь из вершины 1 в вершину n и выведите его, либо -1.

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

В первой строке два числа n и m (2 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵). Далее m строк a b w (1 ≤ w ≤ 10⁶) — неориентированное ребро. Возможны петли и кратные рёбра.

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

-1, если пути нет. Иначе — вершины кратчайшего пути от 1 до n через пробел.

Заметка

Если кратчайших путей несколько, можно вывести любой.

🧪 Тесты#

Тест 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

Тест 2#

Ввод:

3 1
1 2 5

Вывод:

-1

Тест 3#

Ввод:

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

Вывод:

1 3 4

Заметка

Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.

💡 Подсказка#

⬅️ К списку задач уровня