


from __future__ import annotations



def 							UpperCamelCase_( lowerCamelCase_				,					lowerCamelCase_					)       ->		Any:
    print(F'''Vertex\tShortest Distance from vertex {src}'''					)
    for i, d in enumerate(lowerCamelCase_					):
        print(F'''{i}\t\t{d}'''					)



def 							UpperCamelCase_( lowerCamelCase_				,					lowerCamelCase_				,					lowerCamelCase_					)       ->		List[Any]:
    for j in range(lowerCamelCase_					):
        _lowercase						,							_lowercase						,							_lowercase			:				Dict 						=						(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 							UpperCamelCase_( lowerCamelCase_				,					lowerCamelCase_				,					lowerCamelCase_				,					lowerCamelCase_					)       ->		list[float]:
    _lowercase			:				Optional[int] 						=						[float('inf'					)] * vertex_count
    _lowercase			:				str 						=						0.0

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

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

    _lowercase			:				Dict 						=						check_negative_cycle(lowerCamelCase_				,					lowerCamelCase_				,					lowerCamelCase_					)
    if negative_cycle_exists:
        raise Exception('Negative cycle found'					)

    return distance


if __name__ == "__main__":
 import doctest

 doctest.testmod()

 SCREAMING_SNAKE_CASE			: List[str]				   =					int(input("Enter number of vertices: ").strip())
 SCREAMING_SNAKE_CASE			: Union[str, Any]				   =					int(input("Enter number of edges: ").strip())

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

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

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






def 						a__			(				A__ = 5_0_0_0_0_0_0_0				):
			SCREAMING_SNAKE_CASE_		:     Union[str, Any]					=					set()
			SCREAMING_SNAKE_CASE_		:     Optional[int]					=					int((limit - 2_4) ** (1 / 2)				)

			SCREAMING_SNAKE_CASE_		:     Dict					=					set(range(3,      prime_square_limit + 1,      2				)				)
			primes.add(2				)
			for p in range(3,      prime_square_limit + 1,      2				):
						if p not in primes:
									continue
						primes.difference_update(set(range(p * p,      prime_square_limit + 1,      A__				)				)				)

			for primea in primes:
						SCREAMING_SNAKE_CASE_		:     int					=					primea * primea
						for primea in primes:
									SCREAMING_SNAKE_CASE_		:     Dict					=					primea * primea * primea
									if square + cube >= limit - 1_6:
												break
									for primea in primes:
												SCREAMING_SNAKE_CASE_		:     Optional[int]					=					primea * primea * primea * primea
												SCREAMING_SNAKE_CASE_		:     str					=					square + cube + tetr
												if total >= limit:
															break
												ret.add(A__				)

			return len(A__				)


if __name__ == "__main__":
				print(F"""{solution() = }""")





