



from __future__ import annotations

def   lowerCAmelCase__						(							_SCREAMING_SNAKE_CASE       :			list[float]				,     _SCREAMING_SNAKE_CASE       :			List[str]    ):
				"""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   lowerCAmelCase__						(							_SCREAMING_SNAKE_CASE       :			list[dict[str, int]]				,     _SCREAMING_SNAKE_CASE       :			list[float]				,     _SCREAMING_SNAKE_CASE       :			int    ):
				"""simple docstring"""







				for j in range(_SCREAMING_SNAKE_CASE    ):
								__a     ,					__a     ,					__a       =		(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    ):
				"""simple docstring"""







				__a       =		[float("""inf"""    )] * vertex_count
				__a       =		0.0

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

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

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

						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)





def   lowerCAmelCase__						(							_SCREAMING_SNAKE_CASE       :			Tuple				,     _SCREAMING_SNAKE_CASE       :			Tuple				,     _SCREAMING_SNAKE_CASE       :			Tuple=False    ):
				"""simple docstring"""







				if isinstance(_SCREAMING_SNAKE_CASE				,     _SCREAMING_SNAKE_CASE    ) and isinstance(_SCREAMING_SNAKE_CASE				,     _SCREAMING_SNAKE_CASE    ):
								__a       =		len(set_a.intersection(_SCREAMING_SNAKE_CASE    )    )

								if alternative_union:
												__a       =		len(_SCREAMING_SNAKE_CASE    ) + len(_SCREAMING_SNAKE_CASE    )
								else:
												__a       =		len(set_a.union(_SCREAMING_SNAKE_CASE    )    )

								return intersection / union

				if isinstance(_SCREAMING_SNAKE_CASE				,     (list, tuple)    ) and isinstance(_SCREAMING_SNAKE_CASE				,     (list, tuple)    ):
								__a       =		[element for element in set_a if element in set_b]

								if alternative_union:
												__a       =		len(_SCREAMING_SNAKE_CASE    ) + len(_SCREAMING_SNAKE_CASE    )
												return len(_SCREAMING_SNAKE_CASE    ) / union
								else:
												__a       =		set_a + [element for element in set_b if element not in set_a]
												return len(_SCREAMING_SNAKE_CASE    ) / len(_SCREAMING_SNAKE_CASE    )

								return len(_SCREAMING_SNAKE_CASE    ) / len(_SCREAMING_SNAKE_CASE    )
				return None


if __name__ == "__main__":
						lowerCamelCase__			= {"""a""", """b""", """c""", """d""", """e"""}
						lowerCamelCase__			= {"""c""", """d""", """e""", """f""", """h""", """i"""}
						print(jaccard_similarity(set_a, set_b))
