






from __future__ import annotations


def __A    (      __lowerCAmelCase ,		__lowerCAmelCase	)->  Any:





						"""simple docstring"""



						print(F"""Vertex\tShortest Distance from vertex {src}"""	)
						for i, d in enumerate(__lowerCAmelCase	):
												print(F"""{i}\t\t{d}"""	)


def __A    (      __lowerCAmelCase ,		__lowerCAmelCase ,		__lowerCAmelCase	)->  Union[str, Any]:





						"""simple docstring"""



						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    (      __lowerCAmelCase ,		__lowerCAmelCase ,		__lowerCAmelCase ,		__lowerCAmelCase	)->  list[float]:





						"""simple docstring"""



						_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()

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

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

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

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






def 		__A		(	__lowerCamelCase    )      ->       int:
	a										=							0
	while num > 0:
		digit_sum += num % 10
		num //= 10
	return digit_sum





def 		__A		(	__lowerCamelCase = 100    )      ->       int:
	a										=							1
	a										=							2

	for i in range(2							,			max_n + 1    ):
		a										=							pre_numerator
		a										=							2 * i // 3 if i % 3 == 0 else 1
		a										=							cur_numerator
		a										=							e_cont * pre_numerator + temp

	return sum_digits(__lowerCamelCase    )


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

