from __future__ import annotations
def 							lowerCAmelCase(     __lowerCamelCase				,    __lowerCamelCase						):
					print(f'''Vertex\tShortest Distance from vertex {src}'''						)
					for i, d in enumerate(__lowerCamelCase						):
										print(f'''{i}\t\t{d}'''						)
def 							lowerCAmelCase(     __lowerCamelCase				,    __lowerCamelCase				,    __lowerCamelCase						):
					for j in range(__lowerCamelCase						):
										__a ,				__a ,				__a		 =       (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(     __lowerCamelCase				,    __lowerCamelCase				,    __lowerCamelCase				,    __lowerCamelCase						):
					__a		 =       [float('inf'						)] * vertex_count
					__a		 =       0.0

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

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

					__a		 =       check_negative_cycle(__lowerCamelCase				,    __lowerCamelCase				,    __lowerCamelCase						)
					if negative_cycle_exists:
										raise Exception('Negative cycle found'						)

					return distance


if __name__ == "__main__":
	import doctest

	doctest.testmod()

	lowerCamelCase_    :		Union[str, Any]							=	int(input("""Enter number of vertices: """).strip())
	lowerCamelCase_    :		Dict							=	int(input("""Enter number of edges: """).strip())

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

	for i in range(E):
		print("""Edge """, i + 1)
		lowerCamelCase_						,  lowerCamelCase_						,  lowerCamelCase_    :		List[str]							=	(
		    int(x)
		    for x in input("""Enter source, destination, weight: """).strip().split(""" """)
		)
		lowerCamelCase_    :		List[Any]							=	{"""src""": src, """dst""": dest, """weight""": weight}

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





def 							lowerCAmelCase(     __lowerCamelCase						):
					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'						)
					__a		 =       ''
					while len(__lowerCamelCase						) % 3 != 0:
										__a		 =       '0' + bin_string
					__a		 =       [
					    bin_string[index : index + 3]
					    for index in range(len(__lowerCamelCase						)						)
					    if index % 3 == 0
					]
					for bin_group in bin_string_in_3_list:
										__a		 =       0
										for index, val in enumerate(__lowerCamelCase						):
															oct_val += int(2 ** (2 - index) * int(__lowerCamelCase						)						)
										oct_string += str(__lowerCamelCase						)
					return oct_string


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

	testmod()




