






import numpy as np

UpperCamelCase								=		[
    ["a", "b", "c", "d", "e"],
    ["f", "g", "h", "i", "k"],
    ["l", "m", "n", "o", "p"],
    ["q", "r", "s", "t", "u"],
    ["v", "w", "x", "y", "z"],
]

class 				lowerCAmelCase_	:


				def __init__(					self      ):
											_lowercase							:   Any 							=   np.array(_lowerCAmelCase      )


				def 						__a					(					self ,						_lowerCAmelCase      ):
											_lowercase							,							_lowercase							:   List[str] 							=   np.where(letter == self.SQUARE      )
											_lowercase							:   Optional[int] 							=   np.concatenate([indexa + 1, indexa + 1]      )
											return indexes


				def 						__a					(					self ,						_lowerCAmelCase ,						_lowerCAmelCase      ):
											_lowercase							:   int 							=   self.SQUARE[indexa - 1, indexa - 1]
											return letter


				def 						__a					(					self ,						_lowerCAmelCase      ):
											_lowercase							:   int 							=   message.lower()
											_lowercase							:   Optional[Any] 							=   message.replace(' ' ,						''      )
											_lowercase							:   Optional[Any] 							=   message.replace('j' ,						'i'      )

											_lowercase							:   Optional[int] 							=   np.empty((2, len(_lowerCAmelCase      ))      )
											for letter_index in range(len(_lowerCAmelCase      )      ):
																		_lowercase							:   Any 							=   self.letter_to_numbers(message[letter_index]      )

																		_lowercase							:   Tuple 							=   numbers[0]
																		_lowercase							:   int 							=   numbers[1]

											_lowercase							:   int 							=   first_step.reshape(2 * len(_lowerCAmelCase      )      )
											_lowercase							:   Tuple 							=   ''
											for numbers_index in range(len(_lowerCAmelCase      )      ):
																		_lowercase							:   int 							=   int(second_step[numbers_index * 2]      )
																		_lowercase							:   List[Any] 							=   int(second_step[(numbers_index * 2) + 1]      )
																		_lowercase							:   Optional[int] 							=   self.numbers_to_letter(_lowerCAmelCase ,						_lowerCAmelCase      )
																		_lowercase							:   List[Any] 							=   encoded_message + letter

											return encoded_message


				def 						__a					(					self ,						_lowerCAmelCase      ):
											_lowercase							:   Tuple 							=   message.lower()
											message.replace(' ' ,						''      )
											_lowercase							:   Optional[Any] 							=   np.empty(2 * len(_lowerCAmelCase      )      )
											for letter_index in range(len(_lowerCAmelCase      )      ):
																		_lowercase							:   List[Any] 							=   self.letter_to_numbers(message[letter_index]      )
																		_lowercase							:   int 							=   numbers[0]
																		_lowercase							:   Union[str, Any] 							=   numbers[1]

											_lowercase							:   Optional[int] 							=   first_step.reshape((2, len(_lowerCAmelCase      ))      )
											_lowercase							:   Tuple 							=   ''
											for numbers_index in range(len(_lowerCAmelCase      )      ):
																		_lowercase							:   Tuple 							=   int(second_step[0, numbers_index]      )
																		_lowercase							:   Dict 							=   int(second_step[1, numbers_index]      )
																		_lowercase							:   List[Any] 							=   self.numbers_to_letter(_lowerCAmelCase ,						_lowerCAmelCase      )
																		_lowercase							:   Dict 							=   decoded_message + letter

											return decoded_message







import math






class      lowerCamelCase_      :




	def __init__(     self						:     Union[str, Any]					,      __A						:     List[str]=0							):  # a graph with Node 0,1,...,N-1
		__A :			List[str]		    =			n
		__A :			List[str]		    =			[
		    [math.inf for j in range(0					,      __A							)] for i in range(0					,      __A							)
		]  # adjacency matrix for weight
		__A :			str		    =			[
		    [math.inf for j in range(0					,      __A							)] for i in range(0					,      __A							)
		]  # dp[i][j] stores minimum distance from i to j




	def        lowerCAmelCase_       (     self						:     str					,      __A						:     Union[str, Any]					,      __A						:     Any					,      __A						:     Optional[int]							):
		__A :			List[Any]		    =			w




	def        lowerCAmelCase_       (     self						:     Union[str, Any]							):
		for k in range(0					,      self.n							):
			for i in range(0					,      self.n							):
				for j in range(0					,      self.n							):
					__A :			List[Any]		    =			min(self.dp[i][j]					,      self.dp[i][k] + self.dp[k][j]							)




	def        lowerCAmelCase_       (     self						:     int					,      __A						:     List[str]					,      __A						:     List[str]							):
		return self.dp[u][v]


if __name__ == "__main__":
			UpperCAmelCase_							:					Tuple		 =   Graph(5)
			graph.add_edge(0, 2, 9)
			graph.add_edge(0, 4, 10)
			graph.add_edge(1, 3, 5)
			graph.add_edge(2, 3, 7)
			graph.add_edge(3, 0, 10)
			graph.add_edge(3, 1, 2)
			graph.add_edge(3, 2, 1)
			graph.add_edge(3, 4, 6)
			graph.add_edge(4, 1, 3)
			graph.add_edge(4, 2, 4)
			graph.add_edge(4, 3, 9)
			graph.floyd_warshall()
			graph.show_min(1, 4)
			graph.show_min(0, 3)





