
"""simple docstring"""

from __future__ import annotations






def 							A						(				snake_case      :list[float]				,					snake_case      :Optional[int]		)      ->	List[Any]:
 print(f'Vertex\tShortest Distance from vertex {src}'		)
 for i, d in enumerate(lowerCAmelCase__		):
  print(f'{i}\t\t{d}'		)






def 							A						(				snake_case      :list[dict[str, int]]				,					snake_case      :list[float]				,					snake_case      :int		)      ->	int:


 for j in range(lowerCAmelCase__		):
  __UpperCamelCase  ,	__UpperCamelCase  ,	__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 							A						(				snake_case      :list[dict[str, int]]				,					snake_case      :int				,					snake_case      :int				,					snake_case      :int		)      ->	list[float]:
 __UpperCamelCase				  =       [float('inf'		)] * vertex_count
 __UpperCamelCase				  =       0.0

 for _ in range(vertex_count - 1		):
  for j in range(lowerCAmelCase__		):
   __UpperCamelCase  ,	__UpperCamelCase  ,	__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()

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

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

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

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




"""simple docstring"""






from __future__ import annotations

from typing import Any





class  _A						:

      def __init__(						self		,       __lowerCAmelCase = 6						):







            """simple docstring"""



            lowercase														=	None
            lowercase														=	None
            self.create_linked_list(__lowerCAmelCase						)

      def 				A__       (						self		,       __lowerCAmelCase						):







            """simple docstring"""



            lowercase														=	Node()
            lowercase														=	current_node
            lowercase														=	current_node
            lowercase														=	current_node
            for _ in range(1		,       __lowerCAmelCase						):
                  lowercase														=	Node()
                  lowercase														=	current_node
                  lowercase														=	previous_node
                  lowercase														=	current_node
            lowercase														=	self.front
            lowercase														=	previous_node

      def 				A__       (						self						):







            """simple docstring"""



            return (
                self.front == self.rear
                and self.front is not None
                and self.front.data is None
            )

      def 				A__       (						self						):







            """simple docstring"""



            self.check_can_perform_operation()
            return self.front.data if self.front else None

      def 				A__       (						self		,       __lowerCAmelCase						):







            """simple docstring"""



            if self.rear is None:
                  return

            self.check_is_full()
            if not self.is_empty():
                  lowercase														=	self.rear.next
            if self.rear:
                  lowercase														=	data

      def 				A__       (						self						):







            """simple docstring"""



            self.check_can_perform_operation()
            if self.rear is None or self.front is None:
                  return None
            if self.front == self.rear:
                  lowercase														=	self.front.data
                  lowercase														=	None
                  return data

            lowercase														=	self.front
            lowercase														=	old_front.next
            lowercase														=	old_front.data
            lowercase														=	None
            return data

      def 				A__       (						self						):







            """simple docstring"""



            if self.is_empty():
                  raise Exception("""Empty Queue"""						)







      def 				A__       (						self						):







            """simple docstring"""



            if self.rear and self.rear.next == self.front:
                  raise Exception("""Full Queue"""						)






class  _A						:

      def __init__(						self						):







            """simple docstring"""



            lowercase														=	None
            lowercase														=	None
            lowercase														=	None


if __name__ == "__main__":
       import doctest

       doctest.testmod()



