





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



def 				lowerCAmelCase_ (							A_    ,A_):
    UpperCamelCase__:	Optional[Any]					=     [[float("inf") for _ in range(A_)] for _ in range(A_)]

    for i in range(A_):
        for j in range(A_):
            UpperCamelCase__:	int					=     graph[i][j]

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

    _print_dist(A_    ,A_)
    return dist, v


if __name__ == "__main__":
   A__:    str  	=	int(input('''Enter number of vertices: '''))
   A__:    Any  	=	int(input('''Enter number of edges: '''))

   A__:    Optional[int]  	=	[[float('''inf''') for i in range(v)] for j in range(v)]

   for i in range(v):
      A__:    List[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)
      A__:    str  	=	int(input('''Enter source:'''))
      A__:    int  	=	int(input('''Enter destination:'''))
      A__:    Tuple  	=	float(input('''Enter weight:'''))
      A__:    Optional[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








from __future__ import annotations

from typing import Any




class        _a    :

      """simple docstring"""


      def __init__(		self:			Optional[int]	,    __lowerCamelCase:			int					):
          '''simple docstring'''


          UpperCamelCase__:	Optional[Any]					=     num_of_nodes
          UpperCamelCase__:	list[list[int]]					=     []
          UpperCamelCase__:	dict[int, int]					=     {}






      def 			UpperCAmelCase_       (		self:			Any	,    __lowerCamelCase:			int	,    __lowerCamelCase:			int	,    __lowerCamelCase:			int					):
          '''simple docstring'''


          self.m_edges.append([u_node, v_node, weight]					)






      def 			UpperCAmelCase_       (		self:			Dict	,    __lowerCamelCase:			int					):
          '''simple docstring'''


          if self.m_component[u_node] == u_node:
              return u_node
          return self.find_component(self.m_component[u_node]					)






      def 			UpperCAmelCase_       (		self:			str	,    __lowerCamelCase:			int					):
          '''simple docstring'''


          if self.m_component[u_node] != u_node:
              for k in self.m_component:
                  UpperCamelCase__:	Dict					=     self.find_component(__lowerCamelCase					)






      def 			UpperCAmelCase_       (		self:			str	,    __lowerCamelCase:			list[int]	,    __lowerCamelCase:			int	,    __lowerCamelCase:			int					):
          '''simple docstring'''


          if component_size[u_node] <= component_size[v_node]:
              UpperCamelCase__:	List[str]					=     v_node
              component_size[v_node] += component_size[u_node]
              self.set_component(__lowerCamelCase					)

          elif component_size[u_node] >= component_size[v_node]:
              UpperCamelCase__:	Any					=     self.find_component(__lowerCamelCase					)
              component_size[u_node] += component_size[v_node]
              self.set_component(__lowerCamelCase					)






      def 			UpperCAmelCase_       (		self:			Tuple					):
          '''simple docstring'''


          UpperCamelCase__:	Optional[int]					=     []
          UpperCamelCase__:	Optional[int]					=     0

          UpperCamelCase__:	list[Any]					=     [-1] * self.m_num_of_nodes

          # A list of components (initialized to all of the nodes)
          for node in range(self.m_num_of_nodes					):
              self.m_component.update({node: node}					)
              component_size.append(1					)

          UpperCamelCase__:	Optional[int]					=     self.m_num_of_nodes

          while num_of_components > 1:
              for edge in self.m_edges:
                  UpperCamelCase__				, UpperCamelCase__				, UpperCamelCase__:	List[str]					=     edge

                  UpperCamelCase__:	List[Any]					=     self.m_component[u]
                  UpperCamelCase__:	Tuple					=     self.m_component[v]

                  if u_component != v_component:

                      for component in (u_component, v_component):
                          if (
                              minimum_weight_edge[component] == -1
                              or minimum_weight_edge[component][2] > w
                          ):
                              UpperCamelCase__:	Any					=     [u, v, w]

              for edge in minimum_weight_edge:
                  if isinstance(__lowerCamelCase	,    __lowerCamelCase					):
                      UpperCamelCase__				, UpperCamelCase__				, UpperCamelCase__:	List[str]					=     edge

                      UpperCamelCase__:	Tuple					=     self.m_component[u]
                      UpperCamelCase__:	Optional[Any]					=     self.m_component[v]

                      if u_component != v_component:
                          mst_weight += w
                          self.union(__lowerCamelCase	,    __lowerCamelCase	,    __lowerCamelCase					)
                          print(F"Added edge [{u} - {v}]\nAdded weight: {w}\n"					)
                          num_of_components -= 1

              UpperCamelCase__:	List[Any]					=     [-1] * self.m_num_of_nodes
          print(F"The total weight of the minimal spanning tree is: {mst_weight}"					)



def 				lowerCAmelCase_ (							):
    pass


if __name__ == "__main__":
   import doctest

   doctest.testmod()

