Shortest Path using Dijkstra's Algorithm

You are given a directed weighted graph. Each edge is represented by three pieces of information: the source node, the destination node, and the weight of the edge. The first line of the input is the starting node. The remaining lines describe the edges of the graph.

Your task is to use Dijkstra's algorithm to compute the shortest path distances from the starting node to every other node in the graph. If a node is unreachable from the starting node, its distance should be displayed as Infinity.

After computing the distances, print the results in sorted order of the node names (lexicographically). For each node v, output a line in the following format:

Distance from \(s\) to \(v\) is \(d\)

where \(s\) is the starting node and \(d\) is the computed shortest distance (or "Infinity" if unreachable). All numerical comparisons and computations for distances should be done using Dijkstra's algorithm. The weight of each edge is a non-negative integer.

inputFormat

The input is read from standard input (stdin). The first line contains a string representing the starting node. Each subsequent line contains an edge described by three values separated by whitespace: the source node, the destination node, and the weight (a non-negative integer). The input terminates at end-of-file.

outputFormat

For each node in the graph (sorted in lexicographical order), print a line: 'Distance from to is '. If a node is unreachable from the starting node, print 'Infinity' as its distance.## sample

a
a b 4
a c 2
b e 3
c b 1
c d 4
c e 5
d e 1

Distance from a to a is 0
Distance from a to b is 3
Distance from a to c is 2
Distance from a to d is 6
Distance from a to e is 6