
'''simple docstring'''
lowerCAmelCase					:    List[Any]           = [4, 1, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
lowerCAmelCase					:    int           = [3, 7, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
lowerCAmelCase					:    List[Any]           = {
    0: 'Sunday',
    1: 'Monday',
    2: 'Tuesday',
    3: 'Wednesday',
    4: 'Thursday',
    5: 'Friday',
    6: 'Saturday',
}







def 		A_(     A						:		int		,     A						:		int		,     A						:		int):
							assert len(str(A)) > 2, "year should be in YYYY format"
							assert 1 <= month <= 12, "month should be between 1 to 12"
							assert 1 <= day <= 31, "day should be between 1 to 31"

							# Doomsday algorithm:
							UpperCamelCase   			=     year // 100
							UpperCamelCase   			=     (5 * (century % 4) + 2) % 7
							UpperCamelCase   			=     year % 100
							UpperCamelCase   			=     centurian % 12
							UpperCamelCase   			=     (
							    (centurian // 12) + centurian_m + (centurian_m // 4) + century_anchor
							) % 7
							UpperCamelCase   			=     (
							    DOOMSDAY_NOT_LEAP[month - 1]
							    if (year % 4 != 0) or (centurian == 0 and (year % 400) == 0)
							    else DOOMSDAY_LEAP[month - 1]
							)
							UpperCamelCase   			=     (dooms_day + day - day_anchor) % 7
							return WEEK_DAY_NAMES[week_day]


if __name__ == "__main__":
						import doctest

						doctest.testmod()








"""simple docstring"""

from __future__ import annotations


def lowerCAmelCase_   (					UpperCamelCase__						:			list[float]					, UpperCamelCase__						:			Any			):






 """simple docstring"""







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


def lowerCAmelCase_   (					UpperCamelCase__						:			list[dict[str, int]]					, UpperCamelCase__						:			list[float]					, UpperCamelCase__						:			int			):






 """simple docstring"""







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






 """simple docstring"""







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

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

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

 __lowercase						=						check_negative_cycle(UpperCamelCase__					, UpperCamelCase__					, UpperCamelCase__			)
 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)
