






'''simple docstring'''





from __future__ import annotations
def __UpperCAmelCase   (					A					:			list[float]			,       A					:			Any		)    ->   Tuple:
			print(F"Vertex\tShortest Distance from vertex {src}"		)
			for i, d in enumerate(UpperCamelCase__		):
						print(F"{i}\t\t{d}"		)
def __UpperCAmelCase   (					A					:			list[dict[str, int]]			,       A					:			list[float]			,       A					:			int		)    ->   Any:







			for j in range(UpperCamelCase__		):
						UpperCAmelCase_    ,      UpperCAmelCase_    ,      UpperCAmelCase_      :       List[str]          =       (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 __UpperCAmelCase   (					A					:			list[dict[str, int]]			,       A					:			int			,       A					:			int			,       A					:			int		)    ->   Tuple:
			UpperCAmelCase_      :       Tuple          =       [float('''inf'''		)] * vertex_count
			UpperCAmelCase_      :       Optional[Any]          =       0.0

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

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

			UpperCAmelCase_      :       List[Any]          =       check_negative_cycle(UpperCamelCase__			,       UpperCamelCase__			,       UpperCamelCase__		)
			if negative_cycle_exists:
						raise Exception('''Negative cycle found'''		)

			return distance


if __name__ == "__main__":
						import doctest

						doctest.testmod()

						_UpperCamelCase						:						Tuple  =					int(input('Enter number of vertices: ').strip())
						_UpperCamelCase						:						Optional[Any]  =					int(input('Enter number of edges: ').strip())

						_UpperCamelCase						:						Optional[Any]  =					[{} for _ in range(E)]

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

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






"""simple docstring"""

def lowerCAmelCase_   (					UpperCamelCase__						:			int					, UpperCamelCase__						:			int			):






 """simple docstring"""







 return x if y == 0 else greatest_common_divisor(UpperCamelCase__					, x % y			)


def lowerCAmelCase_   (					UpperCamelCase__						:			int					, UpperCamelCase__						:			int			):






 """simple docstring"""







 return (x * y) // greatest_common_divisor(UpperCamelCase__					, UpperCamelCase__			)


def lowerCAmelCase_   (					UpperCamelCase__						:			int = 20			):






 """simple docstring"""







 __lowercase						=						1
 for i in range(1					, n + 1			):
  __lowercase						=						lcm(UpperCamelCase__					, UpperCamelCase__			)
 return g


if __name__ == "__main__":
       print(f"""{solution() = }""")
