



import heapq


def 	_A	(   _UpperCamelCase      ,					_UpperCamelCase      ,					_UpperCamelCase			):
				_UpperCAmelCase						:  Union[str, Any]     					=	[(0, start)]  # cost from start node,end node
				_UpperCAmelCase						:  Optional[int]     					=	set()
				while heap:
								((_UpperCAmelCase)					, (_UpperCAmelCase))						:  List[Any]     					=	heapq.heappop(_UpperCamelCase			)
								if u in visited:
												continue
								visited.add(_UpperCamelCase			)
								if u == end:
												return cost
								for v, c in graph[u]:
												if v in visited:
																continue
												_UpperCAmelCase						:  str     					=	cost + c
												heapq.heappush(_UpperCamelCase      ,					(next_item, v)			)
				return -1


UpperCAmelCase__			:   Tuple      			=    {
    '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__			:   Dict      			=    {
    'B': [['C', 1]],
    'C': [['D', 1]],
    'D': [['F', 1]],
    'E': [['B', 1], ['F', 3]],
    'F': [],
}
UpperCAmelCase__			:   Union[str, Any]      			=    {
    'B': [['C', 1]],
    'C': [['D', 1]],
    'D': [['F', 1]],
    'E': [['B', 1], ['G', 2]],
    'F': [],
    'G': [['F', 1]],
}

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

UpperCAmelCase__			:   Optional[Any]      			=    dijkstra(Ga, 'E', 'F')
print(short_distance)  # E -- 3 --> F == 3

UpperCAmelCase__			:   Optional[Any]      			=    dijkstra(Ga, 'E', 'F')
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
					import doctest

					doctest.testmod()





import math
from timeit import timeit


def 	_A	(   _UpperCamelCase			):
				_UpperCAmelCase						:  str     					=	0
				_UpperCAmelCase						:  Tuple     					=	abs(_UpperCamelCase			)
				while True:
								_UpperCAmelCase						:  str     					=	n // 10
								digits += 1
								if n == 0:
												break
				return digits


def 	_A	(   _UpperCamelCase			):
				return 1 if n == 0 else math.floor(math.log(abs(_UpperCamelCase			)      ,					10			) + 1			)


def 	_A	(   _UpperCamelCase			):
				return len(str(abs(_UpperCamelCase			)			)			)


def 	_A	(   ):
				from collections.abc import Callable

				def benchmark_a_function(_UpperCamelCase      ,					_UpperCamelCase			) -> None:
								_UpperCAmelCase						:  List[str]     					=	F'''{func.__name__}({value})'''
								_UpperCAmelCase						:  Any     					=	timeit(F'''__main__.{call}'''      ,					setup='''import __main__'''			)
								print(F'''{call}: {func(_UpperCamelCase			)} -- {timing} seconds'''			)

				for value in (262_144, 1_125_899_906_842_624, 1_267_650_600_228_229_401_496_703_205_376):
								for func in (num_digits, num_digits_fast, num_digits_faster):
												benchmark_a_function(_UpperCamelCase      ,					_UpperCamelCase			)
								print()


if __name__ == "__main__":
					import doctest

					doctest.testmod()
					benchmark()
