"""

 Name: dijkstra - Dijkstra for the Single Source Shortest Path problem

 Description: dijkstra applies the Dijkstra algorithm for the Single Source Shortest Path problem.

 Author: Eugen Sawin <sawine@me73.com>

 """

 def main():

     args = parse_arguments()

     s = args.source

     raw_graph = args.graph

     graph = [e.strip(' ,(').split(',') for e in raw_graph.split(')')]

     graph = [(e[0].strip(), e[1].strip(), int(e[2].strip())) for e in graph if len(e) == 3]

     distances = dijkstra(s, create_graph(graph))

     for (v, d) in distances.iteritems():

         print '%s: %i' % (v, d)

 def create_graph(desc):

     vertices = set([e[0] for e in desc]) 

     vertices = vertices.union([e[1] for e in desc])

     edges = dict(zip([(v1, v2) for (v1, v2, _) in desc], [c for (_, _, c) in desc]))

     return (vertices, edges)    

 from heapq import *

 def dijkstra(s, (vertices, edges)):

     inf = sum(edges.itervalues()) + 1

     dist = dict([(v, inf) for v in vertices])

     dist[s] = 0

     u = []

     for (v, d) in dist.iteritems():

         heappush(u, (d, v))

     active = vertices

     while len(u) and len(active):

         (_, node) = heappop(u)

         if node in active:

             active.remove(node)

             for (v1, v2) in [e for e in edges.iterkeys() if e[0] == node]:

                 c = edges[(v1, v2)]

                 if dist[v2] > dist[v1] + c:

                     dist[v2] = dist[v1] + c

                     heappush(u, (dist[v2], v2))

     return dist                    

 from argparse import ArgumentParser

 def parse_arguments():

     parser = ArgumentParser(description='Applies the Dijkstra algorithm for the single source shortest path problem.')

     parser.add_argument('graph', help='sequence of (u, v, c(u,v))')

     parser.add_argument('source', help='source vertex')

     return parser.parse_args()

 if __name__ == "__main__":

     main()