

def 	_snake_case		(    SCREAMING_SNAKE_CASE				)       ->      "list[int]":

     """simple docstring"""







     if upper_limit < 0:
          raise ValueError("Limit for the Catalan sequence must be ≥ 0"				)

     _lowerCAmelCase   :					Optional[Any]        =    [0] * (upper_limit + 1)

     # Base case: C(0) = C(1) = 1
     _lowerCAmelCase   :					Optional[int]        =    1
     if upper_limit > 0:
          _lowerCAmelCase   :					Any        =    1

     # Recurrence relation: C(i) = sum(C(j).C(i-j-1)), from j = 0 to i
     for i in range(2		,							upper_limit + 1				):
          for j in range(SCREAMING_SNAKE_CASE				):
               catalan_list[i] += catalan_list[j] * catalan_list[i - j - 1]

     return catalan_list


if __name__ == "__main__":
  print('\n********* Catalan Numbers Using Dynamic Programming ************\n')
  print('\n*** Enter -1 at any time to quit ***')
  print('\nEnter the upper limit (≥ 0) for the Catalan number sequence: ', end='')
  try:
    while True:
      __UpperCAmelCase    				=     int(input().strip())
      if N < 0:
        print('\n********* Goodbye!! ************')
        break
      else:
        print(f'''The Catalan numbers from 0 through {N} are:''')
        print(catalan_numbers(N))
        print('Try another upper limit for the sequence: ', end='')
  except (NameError, ValueError):
    print('\n********* Invalid input, goodbye! ************\n')

  import doctest

  doctest.testmod()









from __future__ import annotations







def 	_snake_case		(    SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)       ->      List[Any]:

     """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 	_snake_case		(    SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)       ->      Tuple:

     """simple docstring"""







     for j in range(SCREAMING_SNAKE_CASE				):
          _lowerCAmelCase      ,			_lowerCAmelCase      ,			_lowerCAmelCase   :					Any        =    (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 	_snake_case		(    SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)       ->      list[float]:

     """simple docstring"""







     _lowerCAmelCase   :					Tuple        =    [float("inf"				)] * vertex_count
     _lowerCAmelCase   :					int        =    0.0

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

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

     _lowerCAmelCase   :					int        =    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()

  __UpperCAmelCase    				=     int(input('Enter number of vertices: ').strip())
  __UpperCAmelCase    				=     int(input('Enter number of edges: ').strip())

  __UpperCAmelCase    				=     [{} for _ in range(E)]

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

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






