






from __future__ import annotations
def 		lowercase__  (				_UpperCamelCase       ,							_UpperCamelCase) ->			str:
      """simple docstring"""

      print(F'Vertex\tShortest Distance from vertex {src}')
      for i, d in enumerate(_UpperCamelCase):
            print(F'{i}\t\t{d}')
def 		lowercase__  (				_UpperCamelCase       ,							_UpperCamelCase       ,							_UpperCamelCase) ->			Dict:
      """simple docstring"""

      for j in range(_UpperCamelCase):
            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 		lowercase__  (				_UpperCamelCase       ,							_UpperCamelCase       ,							_UpperCamelCase       ,							_UpperCamelCase) ->			list[float]:
      """simple docstring"""

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

      for _ in range(vertex_count - 1):
            for j in range(_UpperCamelCase):
                  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(_UpperCamelCase       ,							_UpperCamelCase       ,							_UpperCamelCase)
      if negative_cycle_exists:
            raise Exception('Negative cycle found')

      return distance


if __name__ == "__main__":
       import doctest

       doctest.testmod()

       __magic_name__   :  Optional[Any]        =							int(input('''Enter number of vertices: ''').strip())
       __magic_name__   :  Union[str, Any]        =							int(input('''Enter number of edges: ''').strip())

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

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

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











def 		lowercase__  (				_UpperCamelCase) ->			Any:
      """simple docstring"""

      UpperCamelCase					       =  []
      UpperCamelCase					       =  []
      UpperCamelCase					       =  {
          '^': 3,
          '*': 2,
          '/': 2,
          '%': 2,
          '+': 1,
          '-': 1,
      }  # Priority of each operator
      UpperCamelCase					       =  len(_UpperCamelCase) if (len(_UpperCamelCase) > 7) else 7

      # Print table header for output
      print(
          'Symbol'.center(8)       ,							'Stack'.center(_UpperCamelCase)       ,							'Postfix'.center(_UpperCamelCase)       ,							sep=' | '       ,							)
      print('-' * (print_width * 3 + 7))

      for x in infix:
            if x.isalpha() or x.isdigit():
                  post_fix.append(_UpperCamelCase)  # if x is Alphabet / Digit, add it to Postfix
            elif x == "(":
                  stack.append(_UpperCamelCase)  # if x is "(" push to Stack
            elif x == ")":  # if x is ")" pop stack until "(" is encountered
                  while stack[-1] != "(":
                        post_fix.append(stack.pop())  # Pop stack & add the content to Postfix
                  stack.pop()
            else:
                  if len(_UpperCamelCase) == 0:
                        stack.append(_UpperCamelCase)  # If stack is empty, push x to stack
                  else:  # while priority of x is not > priority of element in the stack
                        while len(_UpperCamelCase) > 0 and priority[x] <= priority[stack[-1]]:
                              post_fix.append(stack.pop())  # pop stack & add to Postfix
                        stack.append(_UpperCamelCase)  # push x to stack

            print(
                x.center(8)       ,							(''.join(_UpperCamelCase)).ljust(_UpperCamelCase)       ,							(''.join(_UpperCamelCase)).ljust(_UpperCamelCase)       ,							sep=' | '       ,							)  # Output in tabular format

      while len(_UpperCamelCase) > 0:  # while stack is not empty
            post_fix.append(stack.pop())  # pop stack & add to Postfix
            print(
                ' '.center(8)       ,							(''.join(_UpperCamelCase)).ljust(_UpperCamelCase)       ,							(''.join(_UpperCamelCase)).ljust(_UpperCamelCase)       ,							sep=' | '       ,							)  # Output in tabular format

      return "".join(_UpperCamelCase)  # return Postfix as str
def 		lowercase__  (				_UpperCamelCase) ->			Optional[Any]:
      """simple docstring"""

      UpperCamelCase					       =  list(infix[::-1])  # reverse the infix equation

      for i in range(len(_UpperCamelCase)):
            if infix[i] == "(":
                  UpperCamelCase					       =  ')'  # change "(" to ")"
            elif infix[i] == ")":
                  UpperCamelCase					       =  '('  # change ")" to "("

      return (infix_2_postfix(''.join(_UpperCamelCase)))[
          ::-1
      ]  # call infix_2_postfix on Infix, return reverse of Postfix


if __name__ == "__main__":
       __magic_name__   :  int        =							input('''\nEnter an Infix Equation = ''')  # Input an Infix equation
       __magic_name__   :  Optional[Any]        =							''''''.join(Infix.split())  # Remove spaces from the input
       print('''\n\t''', Infix, '''(Infix) -> ''', infix_2_prefix(Infix), '''(Prefix)''')



