




def 		lowerCAmelCase_ (						lowerCamelCase						,  lowerCamelCase ):
				print("""\nThe shortest path matrix using Floyd Warshall algorithm\n""" )
				for i in range(lowerCamelCase ):
								for j in range(lowerCamelCase ):
												if dist[i][j] != float("""inf""" ):
																print(int(dist[i][j] )						,  end="""\t""" )
												else:
																print("""INF"""						,  end="""\t""" )
								print()




def 		lowerCAmelCase_ (						lowerCamelCase						,  lowerCamelCase ):
				__magic_name__						:						Tuple										=[[float("""inf""" ) for _ in range(lowerCamelCase )] for _ in range(lowerCamelCase )]

				for i in range(lowerCamelCase ):
								for j in range(lowerCamelCase ):
												__magic_name__						:						Dict										=graph[i][j]

												# check vertex k against all other vertices (i, j)
				for k in range(lowerCamelCase ):
								# looping through rows of graph array
								for i in range(lowerCamelCase ):
												# looping through columns of graph array
												for j in range(lowerCamelCase ):
																if (
																    dist[i][k] != float("""inf""" )
																    and dist[k][j] != float("""inf""" )
																    and dist[i][k] + dist[k][j] < dist[i][j]
																):
																				__magic_name__						:						List[str]										=dist[i][k] + dist[k][j]

				_print_dist(lowerCamelCase						,  lowerCamelCase )
				return dist, v


if __name__ == "__main__":
							UpperCAmelCase_		:					Optional[Any]          =  int(input("Enter number of vertices: "))
							UpperCAmelCase_		:					str          =  int(input("Enter number of edges: "))

							UpperCAmelCase_		:					Optional[Any]          =  [[float("inf") for i in range(v)] for j in range(v)]

							for i in range(v):
														UpperCAmelCase_		:					str          =  0.0

														# src and dst are indices that must be within the array size graph[e][v]
														# failure to follow this will result in an error
							for i in range(e):
														print("\nEdge ", i + 1)
														UpperCAmelCase_		:					Optional[Any]          =  int(input("Enter source:"))
														UpperCAmelCase_		:					Union[str, Any]          =  int(input("Enter destination:"))
														UpperCAmelCase_		:					Dict          =  float(input("Enter weight:"))
														UpperCAmelCase_		:					Union[str, Any]          =  weight

							floyd_warshall(graph, v)

							# Example Input
							# Enter number of vertices: 3
							# Enter number of edges: 2

							# # generated graph from vertex and edge inputs
							# [[inf, inf, inf], [inf, inf, inf], [inf, inf, inf]]
							# [[0.0, inf, inf], [inf, 0.0, inf], [inf, inf, 0.0]]

							# specify source, destination and weight for edge #1
							# Edge  1
							# Enter source:1
							# Enter destination:2
							# Enter weight:2

							# specify source, destination and weight for edge #2
							# Edge  2
							# Enter source:2
							# Enter destination:1
							# Enter weight:1

							# # Expected Output from the vertice, edge and src, dst, weight inputs!!
							# 0		INF	INF
							# INF	0	2
							# INF	1	0












'''simple docstring'''



import os



def  __UpperCAmelCase						(					SCREAMING_SNAKE_CASE__:						str = "matrix.txt"     )	->      int:

   """simple docstring"""
   with open(os.path.join(os.path.dirname(SCREAMING_SNAKE_CASE__     ),       SCREAMING_SNAKE_CASE__     )     ) as in_file:
      __a					  =     in_file.read()

   __a					  =     [[int(SCREAMING_SNAKE_CASE__     ) for cell in row.split(','     )] for row in data.strip().splitlines()]
   __a					  =     [[0 for cell in row] for row in grid]
   __a					  =     len(grid[0]     )

   __a					  =     [[0 for i in range(SCREAMING_SNAKE_CASE__     )] for j in range(SCREAMING_SNAKE_CASE__     )]
   __a					  =     grid[0][0]
   for i in range(1,       SCREAMING_SNAKE_CASE__     ):
      __a					  =     grid[0][i] + dp[0][i - 1]
   for i in range(1,       SCREAMING_SNAKE_CASE__     ):
      __a					  =     grid[i][0] + dp[i - 1][0]

   for i in range(1,       SCREAMING_SNAKE_CASE__     ):
      for j in range(1,       SCREAMING_SNAKE_CASE__     ):
         __a					  =     grid[i][j] + min(dp[i - 1][j],       dp[i][j - 1]     )

   return dp[-1][-1]


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