Taco: Shortest Path Using Dijkstra's Algorithm

This problem requires you to implement Dijkstra's algorithm for finding the shortest paths from a given source node to every other node in a weighted directed graph. The graph is provided with n nodes and m edges. Each edge is defined by three integers u, v, w indicating an edge from node u to node v with weight w. If a node is unreachable from the source, output -1 for that node.

The algorithm uses the following key idea: for each edge from u to v, if the current best distance d[u] satisfies \[ d[v] > d[u] + w \] update d[v] to d[u] + w. Use a priority queue to efficiently determine the next node to process.

Note: All formulas are represented in LaTeX format.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers n and m — the number of nodes and edges respectively.
• Each of the next m lines contains three integers u, v, w representing an edge from node u to node v with weight w.
• The last line contains an integer s representing the source node.

outputFormat

Output the shortest distances from the source node to every node in order (from node 1 to n) to stdout in a single line separated by a space. For each node that is unreachable from the source, output -1.

5 6
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1
1

0 2 3 9 6