




from __future__ import annotations







def 		_A(       UpperCamelCase__							:			int				,       UpperCamelCase__							:			str				)    -> Tuple:
							'''simple docstring'''


							print(F'Vertex\tShortest Distance from vertex {src}'				)
							for i, d in enumerate(SCREAMING_SNAKE_CASE_				):
														print(F'{i}\t\t{d}'				)







def 		_A(       UpperCamelCase__							:			List[str]				,       UpperCamelCase__							:			Union[str, Any]				,       UpperCamelCase__							:			int				)    -> int:
							'''simple docstring'''


							for j in range(SCREAMING_SNAKE_CASE_				):
														__lowercase      =    (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__							:			Tuple				,       UpperCamelCase__							:			List[str]				,       UpperCamelCase__							:			Optional[Any]				,       UpperCamelCase__							:			Union[str, Any]				)    -> list[float]:
							'''simple docstring'''


							__lowercase      =    [float('''inf'''				)] * vertex_count
							__lowercase      =    0.0

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

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

							__lowercase      =    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()

			UpperCAmelCase__				     = int(input("Enter number of vertices: ").strip())
			UpperCAmelCase__				     = int(input("Enter number of edges: ").strip())

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

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

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












from __future__ import annotations







def 		_A(       UpperCamelCase__							:			list[int]				,       UpperCamelCase__							:			list[int]				,       UpperCamelCase__							:			int				)    -> tuple[float, list[float]]:
							'''simple docstring'''


							__lowercase      =    list(range(len(UpperCamelCase__				)				)				)
							__lowercase      =    [v / w for v, w in zip(UpperCamelCase__				,       UpperCamelCase__				)]
							index.sort(key=lambda UpperCamelCase__				: ratio[i]				,       reverse=UpperCamelCase__				)

							__lowercase      =    0
							__lowercase      =    [0] * len(UpperCamelCase__				)
							for i in index:
														if weight[i] <= capacity:
																					__lowercase      =    1
																					max_value += value[i]
																					capacity -= weight[i]
														else:
																					__lowercase      =    capacity / weight[i]
																					max_value += value[i] * capacity / weight[i]
																					break

							return max_value, fractions


if __name__ == "__main__":
			import doctest

			doctest.testmod()






