Shortest Path using Dijkstra's Algorithm

You are given a directed weighted graph and a starting node. The nodes in the graph are labeled with uppercase English letters starting from 'A'. Your task is to compute the shortest path distance from the starting node to every other node in the graph using \(\text{Dijkstra's algorithm}\).

If a node is unreachable from the starting node, output INF for that node.

The graph is provided in the following format: the total number of nodes, the number of edges, the starting node, followed by each edge (source node, destination node, and weight). The answer should be printed in alphabetical order of nodes.

inputFormat

The first line contains an integer (n) representing the total number of nodes. The second line contains an integer (m) representing the number of edges. The third line contains a single uppercase letter representing the starting node. Each of the next (m) lines contains an edge description consisting of two uppercase letters and an integer, which correspond to the source node, destination node, and the weight of the edge respectively.

outputFormat

Print (n) lines. Each line should contain a node (in alphabetical order) followed by its shortest distance from the starting node separated by a space. If a node is unreachable, print 'INF' as its distance.## sample

4
5
A
A B 1
A C 4
B C 2
B D 5
C D 1

A 0
B 1
C 3
D 4