




from __future__ import annotations
def 					lowerCamelCase_    (    SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE   ):
			'''simple docstring'''
			print(f"""Vertex\tShortest Distance from vertex {src}"""   )
			for i, d in enumerate(SCREAMING_SNAKE_CASE   ):
						print(f"""{i}\t\t{d}"""   )
def 					lowerCamelCase_    (    SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE   ):
			'''simple docstring'''
			for j in range(SCREAMING_SNAKE_CASE   ):
						SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE           =					(graph[j][k] for k in ["""src""", """dst""", """weight"""])
						if distance[u] != float("""inf"""   ) and distance[u] + w < distance[v]:
									return True
			return False
def 					lowerCamelCase_    (    SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE   ):
			'''simple docstring'''
			SCREAMING_SNAKE_CASE           =					[float("""inf"""   )] * vertex_count
			SCREAMING_SNAKE_CASE           =					0.0

			for _ in range(vertex_count - 1   ):
						for j in range(SCREAMING_SNAKE_CASE   ):
									SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE           =					(graph[j][k] for k in ["""src""", """dst""", """weight"""])

									if distance[u] != float("""inf"""   ) and distance[u] + w < distance[v]:
												SCREAMING_SNAKE_CASE           =					distance[u] + w

			SCREAMING_SNAKE_CASE           =					check_negative_cycle(SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE   )
			if negative_cycle_exists:
						raise Exception("""Negative cycle found"""   )

			return distance


if __name__ == "__main__":
		import doctest

		doctest.testmod()

		__A						:							Optional[Any]							=  int(input("""Enter number of vertices: """).strip())
		__A						:							List[str]							=  int(input("""Enter number of edges: """).strip())

		__A						:							list[dict[str, int]]							=  [{} for _ in range(E)]

		for i in range(E):
				print("""Edge """, i + 1)
				__A						:							int							=  (
				    int(x)
				    for x in input("""Enter source, destination, weight: """).strip().split(""" """)
				)
				__A						:							Dict							=  {"""src""": src, """dst""": dest, """weight""": weight}

		__A						:							Optional[int]							=  int(input("""\nEnter shortest path source:""").strip())
		__A						:							Any							=  bellman_ford(graph, V, E, source)
		print_distance(shortest_distance, 0)












def 					lowerCamelCase_    (    SCREAMING_SNAKE_CASE   ):
			'''simple docstring'''
			if not all(char in """01""" for char in bin_string   ):
						raise ValueError("""Non-binary value was passed to the function"""   )
			if not bin_string:
						raise ValueError("""Empty string was passed to the function"""   )
			SCREAMING_SNAKE_CASE           =					""""""
			while len(SCREAMING_SNAKE_CASE   ) % 3 != 0:
						SCREAMING_SNAKE_CASE           =					"""0""" + bin_string
			SCREAMING_SNAKE_CASE           =					[
			    bin_string[index : index + 3]
			    for index in range(len(SCREAMING_SNAKE_CASE   )   )
			    if index % 3 == 0
			]
			for bin_group in bin_string_in_3_list:
						SCREAMING_SNAKE_CASE           =					0
						for index, val in enumerate(SCREAMING_SNAKE_CASE   ):
									oct_val += int(2 ** (2 - index) * int(SCREAMING_SNAKE_CASE   )   )
						oct_string += str(SCREAMING_SNAKE_CASE   )
			return oct_string


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

		testmod()






