





from __future__ import annotations



def        __lowercase       (				_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE     )			->       Optional[int]:


      '''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        __lowercase       (				_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE     )			->       List[Any]:


      '''simple docstring'''


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


      '''simple docstring'''


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

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

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

      SCREAMING_SNAKE_CASE		=						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()

      SCREAMING_SNAKE_CASE_						       =	int(input("""Enter number of vertices: """).strip())
      SCREAMING_SNAKE_CASE_						       =	int(input("""Enter number of edges: """).strip())

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

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

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









def        __lowercase       (				_SCREAMING_SNAKE_CASE = 50     )			->       int:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE		=						[1] * (length + 1)

      for row_length in range(3			,						length + 1     ):
            for block_length in range(3			,						row_length + 1     ):
                  for block_start in range(row_length - block_length     ):
                        ways_number[row_length] += ways_number[
                            row_length - block_start - block_length - 1
                        ]

                  ways_number[row_length] += 1

      return ways_number[length]


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


