Problem: You are given an undirected (or directed) weighted graph represented by an adjacency list. Find the shortest distances from a given starting vertex to every other vertex using Dijkstra's algorithm.

Input format: The first line contains two numbers, n and m (1 ≤ n, m ≤ 100,000) – the number of vertices and the number of edges. The next m lines contain triples of integers v, u and w (1 ≤ u, v ≤ n, 0 ≤ w ≤ 1e9) denoting an edge between vertices v and u with weight w. If the graph is undirected, each edge must be added to the adjacency list of both vertices. The last line contains a single number s – the index of the starting vertex.

Output format: In the first line print the distance to every vertex (or some marker if a vertex is unreachable). On the next n lines you may print the paths from the starting vertex to each visited vertex, reconstructing them from the parent array.

Solution: The problem is solved with Dijkstra's algorithm. An array dist is created, where dist[v] holds the currently known shortest distance from the starting vertex to v. The parent array makes it possible to reconstruct the path. Implementations normally use a priority queue (heapq in Python).

Initial condition:

dist = [∞] * n

parent = [-1] * n

Set dist[start] = 0 and push the starting vertex onto the priority queue. Then, while the queue is not empty, pop the vertex with the smallest distance and try to improve the distances to its neighbours.

Once the algorithm finishes, dist[v] holds the shortest distance from start to v (or ∞ if the vertex is unreachable). To reconstruct the path we use parent: