






"""simple docstring"""



from __future__ import annotations

def 			_snake_case    (					lowerCamelCase__     :   list[float]    ,						lowerCamelCase__     :   Union[str, Any]  )    ->     Tuple:
							print(F"""Vertex\tShortest Distance from vertex {src}"""  )
							for i, d in enumerate(lowerCamelCase__  ):
														print(F"""{i}\t\t{d}"""  )

def 			_snake_case    (					lowerCamelCase__     :   list[dict[str, int]]    ,						lowerCamelCase__     :   list[float]    ,						lowerCamelCase__     :   int  )    ->     int:
							for j in range(lowerCamelCase__  ):
														lowerCamelCase_							,						lowerCamelCase_							,						lowerCamelCase_	:							List[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 			_snake_case    (					lowerCamelCase__     :   list[dict[str, int]]    ,						lowerCamelCase__     :   int    ,						lowerCamelCase__     :   int    ,						lowerCamelCase__     :   int  )    ->     list[float]:
							lowerCamelCase_	:							Optional[int]									=[float("inf"  )] * vertex_count
							lowerCamelCase_	:							Union[str, Any]									=0.0

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

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

							lowerCamelCase_	:							Optional[int]									=check_negative_cycle(lowerCamelCase__    ,						lowerCamelCase__    ,						lowerCamelCase__  )
							if negative_cycle_exists:
														raise Exception("Negative cycle found"  )

							return distance


if __name__ == "__main__":
						import doctest

						doctest.testmod()

						A__	:    List[str]			 = int(input('Enter number of vertices: ').strip())
						A__	:    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__ ,						A__ ,						A__	:    Any			 = (
												    int(x)
												    for x in input('Enter source, destination, weight: ').strip().split(' ')
												)
												A__	:    str			 = {'src': src, 'dst': dest, 'weight': weight}

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











"""simple docstring"""



def 			_snake_case    (					lowerCamelCase__     :   list[list[int]]    ,						lowerCamelCase__     :   int    ,						lowerCamelCase__     :   int    ,						lowerCamelCase__     :   list[int]  )    ->     bool:

							# 1. Validate that path exists between current and next vertices
							if graph[path[curr_ind - 1]][next_ver] == 0:
														return False

							# 2. Validate that next vertex is not already in path
							return not any(vertex == next_ver for vertex in path  )

def 			_snake_case    (					lowerCamelCase__     :   list[list[int]]    ,						lowerCamelCase__     :   list[int]    ,						lowerCamelCase__     :   int  )    ->     bool:

							# Base Case
							if curr_ind == len(lowerCamelCase__  ):
														# return whether path exists between current and starting vertices
														return graph[path[curr_ind - 1]][path[0]] == 1

							# Recursive Step
							for next_ver in range(0    ,						len(lowerCamelCase__  )  ):
														if valid_connection(lowerCamelCase__    ,						lowerCamelCase__    ,						lowerCamelCase__    ,						lowerCamelCase__  ):
																					# Insert current vertex  into path as next transition
																					lowerCamelCase_	:							Tuple									=next_ver
																					# Validate created path
																					if util_hamilton_cycle(lowerCamelCase__    ,						lowerCamelCase__    ,						curr_ind + 1  ):
																												return True
																					# Backtrack
																					lowerCamelCase_	:							int									=-1
							return False

def 			_snake_case    (					lowerCamelCase__     :   list[list[int]]    ,						lowerCamelCase__     :   int = 0  )    ->     list[int]:
							lowerCamelCase_	:							Optional[Any]									=[-1] * (len(lowerCamelCase__  ) + 1)
							# initialize start and end of path with starting index
							lowerCamelCase_	:							Optional[int]									=start_index
							# evaluate and if we find answer return path either return empty array
							return path if util_hamilton_cycle(lowerCamelCase__    ,						lowerCamelCase__    ,						1  ) else []



