


'''simple docstring'''



from __future__ import annotations






def   lowerCamelCase							(_SCREAMING_SNAKE_CASE				:       list[float]						,				_SCREAMING_SNAKE_CASE				:       Tuple       ):
					print(F"""Vertex\tShortest Distance from vertex {src}"""       )
					for i, d in enumerate(_SCREAMING_SNAKE_CASE       ):
										print(F"""{i}\t\t{d}"""       )






def   lowerCamelCase							(_SCREAMING_SNAKE_CASE				:       list[dict[str, int]]						,				_SCREAMING_SNAKE_CASE				:       list[float]						,				_SCREAMING_SNAKE_CASE				:       int       ):
					for j in range(_SCREAMING_SNAKE_CASE       ):
										__a   ,    __a   ,    __a      :	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   lowerCamelCase							(_SCREAMING_SNAKE_CASE				:       list[dict[str, int]]						,				_SCREAMING_SNAKE_CASE				:       int						,				_SCREAMING_SNAKE_CASE				:       int						,				_SCREAMING_SNAKE_CASE				:       int       ):
					__a      :	List[str]    =  [float('inf'       )] * vertex_count
					__a      :	Union[str, Any]    =  0.0

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

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

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

					return distance


if __name__ == "__main__":
	import doctest

	doctest.testmod()

	__lowercase     :						Optional[Any]	=     int(input('Enter number of vertices: ').strip())
	__lowercase     :						List[str]	=     int(input('Enter number of edges: ').strip())

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

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

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







'''simple docstring'''



from __future__ import annotations

from dataclasses import dataclass





@dataclass
class 							__UpperCamelCase    :
	A_           =   42
	A_           =   None
	A_           =   None






def   lowerCamelCase							(_SCREAMING_SNAKE_CASE				:       TreeNode | None       ):

					# Validation
					def is_valid_tree(_SCREAMING_SNAKE_CASE				:       TreeNode | None       ) -> bool:
										if node is None:
															return True

										if not isinstance(_SCREAMING_SNAKE_CASE						,				_SCREAMING_SNAKE_CASE       ):
															return False

										try:
															float(node.data       )
										except (TypeError, ValueError):
															return False

										return is_valid_tree(node.left       ) and is_valid_tree(node.right       )

					if not is_valid_tree(_SCREAMING_SNAKE_CASE       ):
										raise ValueError(
										    'Each node should be type of TreeNode and data should be float.'       )

					def is_binary_search_tree_recursive_check(
					    _SCREAMING_SNAKE_CASE				:       TreeNode | None						,				_SCREAMING_SNAKE_CASE				:       float						,				_SCREAMING_SNAKE_CASE				:       float       ) -> bool:

										if node is None:
															return True

										return (
										    left_bound < node.data < right_bound
										    and is_binary_search_tree_recursive_check(node.left						,				_SCREAMING_SNAKE_CASE						,				node.data       )
										    and is_binary_search_tree_recursive_check(
										        node.right						,				node.data						,				_SCREAMING_SNAKE_CASE       )
										)

					return is_binary_search_tree_recursive_check(_SCREAMING_SNAKE_CASE						,				-float('inf'       )						,				float('inf'       )       )


if __name__ == "__main__":
	import doctest

	doctest.testmod()



