Задача: Дан неориентированный (или ориентированный) взвешенный граф, не содержащий кратных ребер и петель, представленный списком смежности. Необходимо найти кратчайшие расстояния от заданной стартовой вершины до всех остальных вершин, используя алгоритм Дейкстры.

Формат входных данных: В первой строке заданы два числа: n и m (1 ≤ n, m ≤ 100,000) – количество вершин и количество рёбер соответственно. В следующих m строках заданы тройки целых чисел v, u и w (1 ≤ u, v ≤ n, 0 ≤ w ≤ 1e9), обозначающие ребро между вершинами v и u с весом w. Если граф неориентированный, каждое ребро нужно добавить в список смежности обеих вершин. Последняя строка содержит одно число s – номер стартовой вершины.

Формат выходных данных: В первой строке выведите расстояния до каждой вершины (или некоторую метку, если вершина недостижима). В следующих n строках можно вывести пути от стартовой вершины до каждой посещённой вершины, восстанавливая их по массиву parent.

Решение: Для решения задачи используется алгоритм Дейкстры. Создаётся массив dist, где dist[v] хранит текущее известное кратчайшее расстояние от стартовой вершины до v. Массив parent позволяет восстановить путь. В реализации обычно используется очередь с приоритетами (heapq в Python).

Начальное условие:

dist = [∞] * n

parent = [-1] * n

Устанавливаем dist[start] = 0, помещаем стартовую вершину в приоритетную очередь. Далее, пока очередь не пуста, извлекаем вершину с наименьшим расстоянием, и пытаемся улучшить расстояния до её соседей.

После выполнения алгоритма в dist[v] будет кратчайшее расстояние от start до v (или ∞, если вершина недостижима). Для восстановления пути используем parent: