




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 ):
								__magic_name__					,			__magic_name__					,			__magic_name__						:						Any										=(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 ):
				__magic_name__						:						Any										=[float("""inf""" )] * vertex_count
				__magic_name__						:						Optional[int]										=0.0

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

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

				__magic_name__						:						Optional[Any]										=check_negative_cycle(lowerCamelCase						,  lowerCamelCase						,  lowerCamelCase )
				if negative_cycle_exists:
								raise Exception("""Negative cycle found""" )

				return distance


if __name__ == "__main__":
							import doctest

							doctest.testmod()

							UpperCAmelCase_		:					Dict          =  int(input("Enter number of vertices: ").strip())
							UpperCAmelCase_		:					Any          =  int(input("Enter number of edges: ").strip())

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

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

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









'''simple docstring'''



from __future__ import annotations
def        UpperCAmelCase (    A	:					list[int]       ,		A	:					int					):
							if len(A					) < k or k < 0:
														raise ValueError('''Invalid Input'''					)
							SCREAMING_SNAKE_CASE       :   Dict         =      sum(array[:k]					)
							for i in range(len(A					) - k					):
														SCREAMING_SNAKE_CASE       :   Optional[Any]         =      current_sum - array[i] + array[i + k]
														SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      max(A       ,		A					)
							return max_sum


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

							testmod()
							lowerCAmelCase_  :							Optional[int]             =    [randint(-1000, 1000) for i in range(100)]
							lowerCAmelCase_  :							Optional[int]             =    randint(0, 110)
							print(f'The maximum sum of {k} consecutive elements is {max_sum_in_array(array,k)}')




