
from __future__ import annotations
class    _UpperCamelCase:

						def __init__(					self		:			List[str]	,						_lowerCamelCase		:			int			):
													_UpperCAmelCase  :			Union[str, Any]	       =		vertices
													_UpperCAmelCase  :			Dict	       =		[[0] * vertices for _ in range(_lowerCamelCase			)]

						def 						a__ (					self		:			str	,						_lowerCamelCase		:			list[int]			):
													print("Vertex \t Distance from Source"			)
													for vertex in range(self.vertices			):
																				print(_lowerCamelCase	,						"\t\t"	,						distances_from_source[vertex]			)

						def 						a__ (					self		:			List[Any]	,						_lowerCamelCase		:			list[int]	,						_lowerCamelCase		:			list[bool]			):
													_UpperCAmelCase  :			Union[str, Any]	       =		1E7
													_UpperCAmelCase  :			int	       =		0

													# Search not nearest vertex not in the shortest path tree
													for vertex in range(self.vertices			):
																				if distances_from_source[vertex] < minimum and visited[vertex] is False:
																											_UpperCAmelCase  :			Union[str, Any]	       =		distances_from_source[vertex]
																											_UpperCAmelCase  :			List[Any]	       =		vertex
													return min_index






						def 						a__ (					self		:			Optional[int]	,						_lowerCamelCase		:			int			):
													_UpperCAmelCase  :			Dict	       =		[int(1E7			)] * self.vertices  # distances from the source
													_UpperCAmelCase  :			Union[str, Any]	       =		0
													_UpperCAmelCase  :			Optional[Any]	       =		[False] * self.vertices

													for _ in range(self.vertices			):
																				_UpperCAmelCase  :			List[Any]	       =		self.minimum_distance(_lowerCamelCase	,						_lowerCamelCase			)
																				_UpperCAmelCase  :			Tuple	       =		True

																				# Update dist value of the adjacent vertices
																				# of the picked vertex only if the current
																				# distance is greater than new distance and
																				# the vertex in not in the shortest path tree
																				for v in range(self.vertices			):
																											if (
																											    self.graph[u][v] > 0
																											    and visited[v] is False
																											    and distances[v] > distances[u] + self.graph[u][v]
																											):
																																		_UpperCAmelCase  :			Optional[Any]	       =		distances[u] + self.graph[u][v]

													self.print_solution(_lowerCamelCase			)


if __name__ == "__main__":
				__lowerCamelCase								=					Graph(9)
				__lowerCamelCase								=					[
				    [0, 4, 0, 0, 0, 0, 0, 8, 0],
				    [4, 0, 8, 0, 0, 0, 0, 1_1, 0],
				    [0, 8, 0, 7, 0, 4, 0, 0, 2],
				    [0, 0, 7, 0, 9, 1_4, 0, 0, 0],
				    [0, 0, 0, 9, 0, 1_0, 0, 0, 0],
				    [0, 0, 4, 1_4, 1_0, 0, 2, 0, 0],
				    [0, 0, 0, 0, 0, 2, 0, 1, 6],
				    [8, 1_1, 0, 0, 0, 0, 1, 0, 7],
				    [0, 0, 2, 0, 0, 0, 6, 7, 0],
				]
				graph.dijkstra(0)






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

							"""simple docstring"""






							if power < 0:
														return -1
							base %= mod
							_UpperCAmelCase  :			Optional[Any]	       =		1

							while power > 0:
														if power & 1:
																					_UpperCAmelCase  :			Optional[Any]	       =		(result * base) % mod
														_UpperCAmelCase  :			List[str]	       =		power >> 1
														_UpperCAmelCase  :			Optional[int]	       =		(base * base) % mod

							return result




def 		lowerCAmelCase_     (     )   ->      List[str]:

							"""simple docstring"""






							print(modular_exponential(3      ,	2_0_0      ,	1_3  )  )


if __name__ == "__main__":
				import doctest

				doctest.testmod()

				main()




