'''simple docstring'''





from __future__ import annotations





def 	lowerCAmelCase_				(					snake_case_       : list[float]					,    snake_case_       : Optional[int]			)    ->      Tuple:


     '''simple docstring'''




     print(f"""Vertex\tShortest Distance from vertex {src}"""			)
     for i, d in enumerate(__lowerCamelCase			):
          print(f"""{i}\t\t{d}"""			)





def 	lowerCAmelCase_				(					snake_case_       : list[dict[str, int]]					,    snake_case_       : list[float]					,    snake_case_       : int			)    ->      Tuple:


     '''simple docstring'''




     for j in range(__lowerCamelCase			):
          UpperCAmelCase_           =   (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_				(					snake_case_       : list[dict[str, int]]					,    snake_case_       : int					,    snake_case_       : int					,    snake_case_       : int			)    ->      Tuple:


     '''simple docstring'''




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

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

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

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

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











'''simple docstring'''


import math
def 							UpperCAmelCase_  (						__lowerCamelCase					:					int ):
   lowercase_			:Dict    			= []
   lowercase_			:List[Any]    			= 2
   lowercase_			:Optional[Any]    			= int(math.sqrt(__lowerCamelCase ) )  # Size of every segment
   lowercase_			:Optional[Any]    			= [True] * (end + 1)
   lowercase_			:Dict    			= []

   while start <= end:
      if temp[start] is True:
         in_prime.append(__lowerCamelCase )
         for i in range(start * start	,end + 1	,__lowerCamelCase ):
            lowercase_			:List[str]    			= False
      start += 1
   prime += in_prime

   lowercase_			:Dict    			= end + 1
   lowercase_			:Dict    			= min(2 * end	,__lowerCamelCase )

   while low <= n:
      lowercase_			:Any    			= [True] * (high - low + 1)
      for each in in_prime:
         lowercase_			:List[Any]    			= math.floor(low / each ) * each
         if t < low:
            t += each

         for j in range(__lowerCamelCase	,high + 1	,__lowerCamelCase ):
            lowercase_			:str    			= False

      for j in range(len(__lowerCamelCase ) ):
         if temp[j] is True:
            prime.append(j + low )

      lowercase_			:Dict    			= high + 1
      lowercase_			:Dict    			= min(high + end	,__lowerCamelCase )

   return prime


print(sieve(10**6))


