






"""simple docstring"""





from __future__ import annotations



def   a    (     __UpperCAmelCase      :    list[float]      ,   __UpperCAmelCase      :    Any  )    ->							Optional[Any]:
						print(f'Vertex\tShortest Distance from vertex {src}'  )
						for i, d in enumerate(__UpperCAmelCase  ):
												print(f'{i}\t\t{d}'  )



def   a    (     __UpperCAmelCase      :    list[dict[str, int]]      ,   __UpperCAmelCase      :    list[float]      ,   __UpperCAmelCase      :    int  )    ->							int:
						for j in range(__UpperCAmelCase  ):
												__magic_name__,			__magic_name__,			__magic_name__:	Dict							=       (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   a    (     __UpperCAmelCase      :    list[dict[str, int]]      ,   __UpperCAmelCase      :    int      ,   __UpperCAmelCase      :    int      ,   __UpperCAmelCase      :    int  )    ->							list[float]:
						__magic_name__:	List[Any]							=       [float("""inf"""  )] * vertex_count
						__magic_name__:	Tuple							=       0.0

						for _ in range(vertex_count - 1  ):
												for j in range(__UpperCAmelCase  ):
																		__magic_name__,			__magic_name__,			__magic_name__:	Union[str, Any]							=       (graph[j][k] for k in ["""src""", """dst""", """weight"""])

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

						__magic_name__:	List[str]							=       check_negative_cycle(__UpperCAmelCase      ,   __UpperCAmelCase      ,   __UpperCAmelCase  )
						if negative_cycle_exists:
												raise Exception("""Negative cycle found"""  )

						return distance


if __name__ == "__main__":
							import doctest

							doctest.testmod()

							__lowerCamelCase							=  int(input('Enter number of vertices: ').strip())
							__lowerCamelCase							=  int(input('Enter number of edges: ').strip())

							__lowerCamelCase							=  [{} for _ in range(E)]

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

							__lowerCamelCase							=  int(input('\nEnter shortest path source:').strip())
							__lowerCamelCase							=  bellman_ford(graph, V, E, source)
							print_distance(shortest_distance, 0)











"""simple docstring"""





def   a    (     __UpperCAmelCase      :    int = 1_0_0  )    ->							int:
						__magic_name__:	str							=       0
						__magic_name__:	Any							=       0
						for i in range(1      ,   n + 1  ):
												sum_of_squares += i**2
												sum_of_ints += i
						return sum_of_ints**2 - sum_of_squares


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



