from __future__ import annotations

from collections.abc import Iterator
from typing import Any
class 							a_					:






 '''simple docstring'''






 def __init__(     self   :    Any     ,       lowercase__   :    Dict):







        '''simple docstring'''



        lowerCAmelCase__	      =   data
        lowerCAmelCase__	      =   None




 def __str__(     self   :    str):







        '''simple docstring'''



        return F"""{self.data}"""






class 							a_					:






 '''simple docstring'''






 def __init__(     self   :    Dict):







        '''simple docstring'''



        lowerCAmelCase__	      =   None
        lowerCAmelCase__	      =   None




 def __iter__(     self   :    List[Any]):







        '''simple docstring'''



        lowerCAmelCase__	      =   self.front
        while node:
               yield node.data
               lowerCAmelCase__	      =   node.next




 def __len__(     self   :    List[Any]):







        '''simple docstring'''



        return len(tuple(iter(self)))




 def __str__(     self   :    Dict):







        '''simple docstring'''



        return " <- ".join(str(lowerCAmelCase__) for item in self)




 def 						__snake_case		(     self   :    int):







        '''simple docstring'''



        return len(self) == 0




 def 						__snake_case		(     self   :    Optional[int]     ,       lowercase__   :    Any):







        '''simple docstring'''



        lowerCAmelCase__	      =   Node(lowerCAmelCase__)
        if self.is_empty():
               lowerCAmelCase__	      =   lowerCAmelCase__	      =   node
        else:
               assert isinstance(self.rear     ,       lowerCAmelCase__)
               lowerCAmelCase__	      =   node
               lowerCAmelCase__	      =   node




 def 						__snake_case		(     self   :    str):







        '''simple docstring'''



        if self.is_empty():
               raise IndexError('dequeue from empty queue')
        assert isinstance(self.front     ,       lowerCAmelCase__)
        lowerCAmelCase__	      =   self.front
        lowerCAmelCase__	      =   self.front.next
        if self.front is None:
               lowerCAmelCase__	      =   None
        return node.data




 def 						__snake_case		(     self   :    Any):







        '''simple docstring'''



        lowerCAmelCase__	      =   lowerCAmelCase__	      =   None


if __name__ == "__main__":
    from doctest import testmod

    testmod()

import heapq

def 				UpperCamelCase					(     lowerCAmelCase_							,       lowerCAmelCase_							,       lowerCAmelCase_ )		->    Dict:




       '''simple docstring'''






       _A=						[(0, start)]  # cost from start node,end node
       _A=						set()
       while heap:
              ((_A),      (_A))=						heapq.heappop(lowerCAmelCase_ )
              if u in visited:
                     continue
              visited.add(lowerCAmelCase_ )
              if u == end:
                     return cost
              for v, c in graph[u]:
                     if v in visited:
                            continue
                     _A=						cost + c
                     heapq.heappush(lowerCAmelCase_							,       (next_item, v) )
       return -1


UpperCAmelCase_    		=				{
    '''A''': [['''B''', 2], ['''C''', 5]],
    '''B''': [['''A''', 2], ['''D''', 3], ['''E''', 1], ['''F''', 1]],
    '''C''': [['''A''', 5], ['''F''', 3]],
    '''D''': [['''B''', 3]],
    '''E''': [['''B''', 4], ['''F''', 3]],
    '''F''': [['''C''', 3], ['''E''', 3]],
}
UpperCAmelCase_    		=				{
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''F''', 3]],
    '''F''': [],
}
UpperCAmelCase_    		=				{
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''G''', 2]],
    '''F''': [],
    '''G''': [['''F''', 1]],
}

UpperCAmelCase_    		=				dijkstra(G, '''E''', '''C''')
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

UpperCAmelCase_    		=				dijkstra(Ga, '''E''', '''F''')
print(short_distance)  # E -- 3 --> F == 3

UpperCAmelCase_    		=				dijkstra(Ga, '''E''', '''F''')
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
      import doctest

      doctest.testmod()