




'''simple docstring'''

from __future__ import annotations


def __UpperCAmelCase	(   _UpperCAmelCase		:   list[float]		,				_UpperCAmelCase		:   int						)      ->      List[Any]:
			print(F'''Vertex\tShortest Distance from vertex {src}'''						)
			for i, d in enumerate(_UpperCAmelCase						):
						print(F'''{i}\t\t{d}'''						)


def __UpperCAmelCase	(   _UpperCAmelCase		:   list[dict[str, int]]		,				_UpperCAmelCase		:   list[float]		,				_UpperCAmelCase		:   int						)      ->      Union[str, Any]:
			for j in range(_UpperCAmelCase						):
						__snake_case		,     __snake_case		,     __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 __UpperCAmelCase	(   _UpperCAmelCase		:   list[dict[str, int]]		,				_UpperCAmelCase		:   int		,				_UpperCAmelCase		:   int		,				_UpperCAmelCase		:   int						)      ->      list[float]:
			__snake_case			=		[float("inf"						)] * vertex_count
			__snake_case			=		0.0

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

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

			__snake_case			=		check_negative_cycle(_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase						)
			if negative_cycle_exists:
						raise Exception("Negative cycle found"						)

			return distance


if __name__ == "__main__":
						import doctest

						doctest.testmod()

						a       :						int								=		int(input('''Enter number of vertices: ''').strip())
						a       :						List[str]								=		int(input('''Enter number of edges: ''').strip())

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

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

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









from __future__ import annotations






class      UpperCamelCase:


					def __init__(    self						:		Optional[int]  ,     SCREAMING_SNAKE_CASE						:		str  ,     SCREAMING_SNAKE_CASE						:		str    )      ->						str:




											'''simple docstring'''

											__snake_case		,       __snake_case				=		text, pattern
											__snake_case		,       __snake_case				=		len(SCREAMING_SNAKE_CASE    ), len(SCREAMING_SNAKE_CASE    )


					def 				SCREAMING_SNAKE_CASE_	(    self						:		Optional[Any]  ,     SCREAMING_SNAKE_CASE						:		str    )      ->						int:




											'''simple docstring'''

											for i in range(self.patLen - 1  ,     -1  ,     -1    ):
																	if char == self.pattern[i]:
																							return i
											return -1


					def 				SCREAMING_SNAKE_CASE_	(    self						:		int  ,     SCREAMING_SNAKE_CASE						:		int    )      ->						int:




											'''simple docstring'''

											for i in range(self.patLen - 1  ,     -1  ,     -1    ):
																	if self.pattern[i] != self.text[current_pos + i]:
																							return current_pos + i
											return -1






					def 				SCREAMING_SNAKE_CASE_	(    self						:		List[Any]    )      ->						list[int]:




											'''simple docstring'''

											__snake_case				=		[]
											for i in range(self.textLen - self.patLen + 1    ):
																	__snake_case				=		self.mismatch_in_text(SCREAMING_SNAKE_CASE    )
																	if mismatch_index == -1:
																							positions.append(SCREAMING_SNAKE_CASE    )
																	else:
																							__snake_case				=		self.match_in_pattern(self.text[mismatch_index]    )
																							__snake_case				=		(
																							    mismatch_index - match_index
																							)  # shifting index lgtm [py/multiple-definition]
											return positions




A				:       str      =  'ABAABA'
A				:       Optional[Any]      =  'AB'
A				:       Any      =  BoyerMooreSearch(text, pattern)
A				:       Tuple      =  bms.bad_character_heuristic()

if len(positions) == 0:
	print('No match found')
else:
	print('Pattern found in following positions: ')
	print(positions)





