





import heapq







def    UpperCAmelCase				(  _lowerCamelCase   :	List[Any]      , _lowerCamelCase   :	Optional[int]      , _lowerCamelCase   :	Optional[int]  ):





						'''simple docstring'''


						SCREAMING_SNAKE_CASE__  :					Any =       [(0, start)]  # cost from start node,end node
						SCREAMING_SNAKE_CASE__  :					Optional[int] =       set()
						while heap:
												((SCREAMING_SNAKE_CASE__),				(SCREAMING_SNAKE_CASE__))  :					Optional[Any] =       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
																		SCREAMING_SNAKE_CASE__  :					Tuple =       cost + c
																		heapq.heappush(_lowerCamelCase      , (next_item, v)  )
						return -1


__lowercase							:Any							=	{
    "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]],
}
__lowercase							:str							=	{
    "B": [["C", 1]],
    "C": [["D", 1]],
    "D": [["F", 1]],
    "E": [["B", 1], ["F", 3]],
    "F": [],
}
__lowercase							:List[str]							=	{
    "B": [["C", 1]],
    "C": [["D", 1]],
    "D": [["F", 1]],
    "E": [["B", 1], ["G", 2]],
    "F": [],
    "G": [["F", 1]],
}

__lowercase							:Optional[int]							=	dijkstra(G, "E", "C")
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

__lowercase							:List[Any]							=	dijkstra(Ga, "E", "F")
print(short_distance)  # E -- 3 --> F == 3

__lowercase							:Dict							=	dijkstra(Ga, "E", "F")
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
				import doctest

				doctest.testmod()






from __future__ import annotations

from collections.abc import Iterable
from dataclasses import dataclass
from typing import Any



class  _a  :






							"""simple docstring"""

							snake_case_							=    ("_front", "_back", "_len")



							@dataclass
							class  _a  :






														"""simple docstring"""

														snake_case_							=    None
														snake_case_							=    None
														snake_case_							=    None







							class  _a  :






														"""simple docstring"""

														snake_case_							=    ("_cur",)

														def __init__(   self					:  Tuple				,						a					:  Deque._Node | None     )						->None:
																				SCREAMING_SNAKE_CASE__  :					Union[str, Any] =       cur

														def __iter__(   self					:  Dict     )						->Deque._Iterator:
																				return self






														def   A_	(   self					:  int     )						->Any:
																				if self._cur is None:
																										# finished iterating
																										raise StopIteration
																				SCREAMING_SNAKE_CASE__  :					Tuple =       self._cur.val
																				SCREAMING_SNAKE_CASE__  :					int =       self._cur.next_node

																				return val







							def __init__(   self					:  str				,						a					:  Iterable[Any] | None = None     )						->None:
													SCREAMING_SNAKE_CASE__  :					Any =       None
													SCREAMING_SNAKE_CASE__  :					Any =       None
													SCREAMING_SNAKE_CASE__  :					int =       0

													if iterable is not None:
																			# append every value to the deque
																			for val in iterable:
																									self.append(a     )

							def   A_	(   self					:  Tuple				,						a					:  Any     )						->None:
													SCREAMING_SNAKE_CASE__  :					Optional[Any] =       self._Node(a				,						a				,						a     )
													if self.is_empty():
																			# front = back
																			SCREAMING_SNAKE_CASE__  :					int =       node
																			SCREAMING_SNAKE_CASE__  :					Dict =       1
													else:
																			# connect nodes
																			SCREAMING_SNAKE_CASE__  :					Optional[int] =       node
																			SCREAMING_SNAKE_CASE__  :					Any =       self._back
																			SCREAMING_SNAKE_CASE__  :					Tuple =       node  # assign new back to the new node

																			self._len += 1

																			# make sure there were no errors
																			assert not self.is_empty(), "Error on appending value."

							def   A_	(   self					:  List[str]				,						a					:  Any     )						->None:
													SCREAMING_SNAKE_CASE__  :					List[Any] =       self._Node(a				,						a				,						a     )
													if self.is_empty():
																			# front = back
																			SCREAMING_SNAKE_CASE__  :					str =       node
																			SCREAMING_SNAKE_CASE__  :					Dict =       1
													else:
																			# connect nodes
																			SCREAMING_SNAKE_CASE__  :					Any =       self._front
																			SCREAMING_SNAKE_CASE__  :					Tuple =       node
																			SCREAMING_SNAKE_CASE__  :					int =       node  # assign new front to the new node

																			self._len += 1

																			# make sure there were no errors
																			assert not self.is_empty(), "Error on appending value."

							def   A_	(   self					:  Dict				,						a					:  Iterable[Any]     )						->None:
													for val in iterable:
																			self.append(a     )

							def   A_	(   self					:  Tuple				,						a					:  Iterable[Any]     )						->None:
													for val in iterable:
																			self.appendleft(a     )

							def   A_	(   self					:  Any     )						->Any:
													assert not self.is_empty(), "Deque is empty."

													SCREAMING_SNAKE_CASE__  :					List[Any] =       self._back
													SCREAMING_SNAKE_CASE__  :					Optional[int] =       self._back.prev_node  # set new back
													# drop the last node - python will deallocate memory automatically
													SCREAMING_SNAKE_CASE__  :					Union[str, Any] =       None

													self._len -= 1

													return topop.val

							def   A_	(   self					:  Any     )						->Any:
													assert not self.is_empty(), "Deque is empty."

													SCREAMING_SNAKE_CASE__  :					Any =       self._front
													SCREAMING_SNAKE_CASE__  :					Dict =       self._front.next_node  # set new front and drop the first node
													SCREAMING_SNAKE_CASE__  :					Dict =       None

													self._len -= 1

													return topop.val

							def   A_	(   self					:  str     )						->bool:
													return self._front is None

							def __len__(   self					:  List[str]     )						->int:
													return self._len

							def __eq__(   self					:  List[Any]				,						a					:  object     )						->bool:

													if not isinstance(a				,						a     ):
																			return NotImplemented

													SCREAMING_SNAKE_CASE__  :					List[Any] =       self._front
													SCREAMING_SNAKE_CASE__  :					Union[str, Any] =       other._front

													# if the length of the dequeues are not the same, they are not equal
													if len(self     ) != len(a     ):
																			return False

													while me is not None and oth is not None:
																			# compare every value
																			if me.val != oth.val:
																									return False
																			SCREAMING_SNAKE_CASE__  :					Any =       me.next_node
																			SCREAMING_SNAKE_CASE__  :					Any =       oth.next_node

													return True

							def __iter__(   self					:  Any     )						->Deque._Iterator:
													return Deque._Iterator(self._front     )






							def __repr__(   self					:  Any     )						->str:
													SCREAMING_SNAKE_CASE__  :					Union[str, Any] =       []
													SCREAMING_SNAKE_CASE__  :					int =       self._front
													while aux is not None:
																			# append the values in a list to display
																			values_list.append(aux.val     )
																			SCREAMING_SNAKE_CASE__  :					Union[str, Any] =       aux.next_node

													return f"""[{', '.join(repr(a     ) for val in values_list     )}]"""


if __name__ == "__main__":
				import doctest

				doctest.testmod()