





import sys
from collections import defaultdict

class 		UpperCamelCase__			:



     '''simple docstring'''

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




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						[]






     def     SCREAMING_SNAKE_CASE__  (							self						:   int						,lowerCamelCase__						:   Dict	)					->		List[str]:




           '''simple docstring'''


           return self.node_position[vertex]






     def     SCREAMING_SNAKE_CASE__  (							self						:   Union[str, Any]						,lowerCamelCase__						:   List[str]						,lowerCamelCase__						:   int	)					->		Any:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						pos






     def     SCREAMING_SNAKE_CASE__  (							self						:   Tuple						,lowerCamelCase__						:   Optional[int]						,lowerCamelCase__						:   int						,lowerCamelCase__						:   List[Any]						,lowerCamelCase__						:   List[str]	)					->		int:




           '''simple docstring'''


           if start > size // 2 - 1:
                 return
           else:
                 if 2 * start + 2 >= size:
                       SCREAMING_SNAKE_CASE		=						2 * start + 1
                 else:
                       if heap[2 * start + 1] < heap[2 * start + 2]:
                             SCREAMING_SNAKE_CASE		=						2 * start + 1
                       else:
                             SCREAMING_SNAKE_CASE		=						2 * start + 2
                 if heap[smallest_child] < heap[start]:
                       SCREAMING_SNAKE_CASE, SCREAMING_SNAKE_CASE		=						heap[smallest_child], positions[smallest_child]
                       SCREAMING_SNAKE_CASE, SCREAMING_SNAKE_CASE		=						(
                           heap[start],
                           positions[start],
                       )
                       SCREAMING_SNAKE_CASE, SCREAMING_SNAKE_CASE		=						temp, tempa

                       SCREAMING_SNAKE_CASE		=						self.get_position(positions[smallest_child]	)
                       self.set_position(
                           positions[smallest_child]						,self.get_position(positions[start]	)	)
                       self.set_position(positions[start]						,lowerCamelCase__	)

                       self.top_to_bottom(lowerCamelCase__						,lowerCamelCase__						,lowerCamelCase__						,lowerCamelCase__	)






     def     SCREAMING_SNAKE_CASE__  (							self						:   Union[str, Any]						,lowerCamelCase__						:   Optional[Any]						,lowerCamelCase__						:   str						,lowerCamelCase__						:   Union[str, Any]						,lowerCamelCase__						:   List[str]	)					->		Tuple:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						position[index]

           while index != 0:
                 SCREAMING_SNAKE_CASE		=						int((index - 2) / 2	) if index % 2 == 0 else int((index - 1) / 2	)

                 if val < heap[parent]:
                       SCREAMING_SNAKE_CASE		=						heap[parent]
                       SCREAMING_SNAKE_CASE		=						position[parent]
                       self.set_position(position[parent]						,lowerCamelCase__	)
                 else:
                       SCREAMING_SNAKE_CASE		=						val
                       SCREAMING_SNAKE_CASE		=						temp
                       self.set_position(lowerCamelCase__						,lowerCamelCase__	)
                       break
                 SCREAMING_SNAKE_CASE		=						parent
           else:
                 SCREAMING_SNAKE_CASE		=						val
                 SCREAMING_SNAKE_CASE		=						temp
                 self.set_position(lowerCamelCase__						,0	)






     def     SCREAMING_SNAKE_CASE__  (							self						:   List[str]						,lowerCamelCase__						:   List[Any]						,lowerCamelCase__						:   List[Any]	)					->		str:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						len(lowerCamelCase__	) // 2 - 1
           for i in range(lowerCamelCase__						,-1						,-1	):
                 self.top_to_bottom(lowerCamelCase__						,lowerCamelCase__						,len(lowerCamelCase__	)						,lowerCamelCase__	)






     def     SCREAMING_SNAKE_CASE__  (							self						:   List[Any]						,lowerCamelCase__						:   Any						,lowerCamelCase__						:   str	)					->		str:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						positions[0]
           SCREAMING_SNAKE_CASE		=						sys.maxsize
           self.top_to_bottom(lowerCamelCase__						,0						,len(lowerCamelCase__	)						,lowerCamelCase__	)
           return temp



def        __lowercase       (				_SCREAMING_SNAKE_CASE     )			->       Union[str, Any]:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE		=						Heap()

      SCREAMING_SNAKE_CASE		=						[0] * len(_SCREAMING_SNAKE_CASE     )
      SCREAMING_SNAKE_CASE		=						[-1] * len(_SCREAMING_SNAKE_CASE     )  # Neighboring Tree Vertex of selected vertex
      # Minimum Distance of explored vertex with neighboring vertex of partial tree
      # formed in graph
      SCREAMING_SNAKE_CASE		=						[]  # Heap of Distance of vertices from their neighboring vertex
      SCREAMING_SNAKE_CASE		=						[]

      for vertex in range(len(_SCREAMING_SNAKE_CASE     )     ):
            distance_tv.append(sys.maxsize     )
            positions.append(_SCREAMING_SNAKE_CASE     )
            heap.node_position.append(_SCREAMING_SNAKE_CASE     )

      SCREAMING_SNAKE_CASE		=						[]
      SCREAMING_SNAKE_CASE		=						1
      SCREAMING_SNAKE_CASE		=						sys.maxsize
      for neighbor, distance in adjacency_list[0]:
            SCREAMING_SNAKE_CASE		=						0
            SCREAMING_SNAKE_CASE		=						distance
      heap.heapify(_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE     )

      for _ in range(1			,						len(_SCREAMING_SNAKE_CASE     )     ):
            SCREAMING_SNAKE_CASE		=						heap.delete_minimum(_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE     )
            if visited[vertex] == 0:
                  tree_edges.append((nbr_tv[vertex], vertex)     )
                  SCREAMING_SNAKE_CASE		=						1
                  for neighbor, distance in adjacency_list[vertex]:
                        if (
                            visited[neighbor] == 0
                            and distance < distance_tv[heap.get_position(_SCREAMING_SNAKE_CASE     )]
                        ):
                              SCREAMING_SNAKE_CASE		=						distance
                              heap.bottom_to_top(
                                  _SCREAMING_SNAKE_CASE			,						heap.get_position(_SCREAMING_SNAKE_CASE     )			,						_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE     )
                              SCREAMING_SNAKE_CASE		=						vertex
      return tree_edges


if __name__ == "__main__":  # pragma: no cover
      # < --------- Prims Algorithm --------- >
      SCREAMING_SNAKE_CASE_						       =	int(input("""Enter number of edges: """).strip())
      SCREAMING_SNAKE_CASE_						       =	defaultdict(list)
      for _ in range(edges_number):
            SCREAMING_SNAKE_CASE_						       =	[int(x) for x in input().strip().split()]
            adjacency_list[edge[0]].append([edge[1], edge[2]])
            adjacency_list[edge[1]].append([edge[0], edge[2]])
      print(prisms_algorithm(adjacency_list))









class 		UpperCamelCase__			:



     '''simple docstring'''

     def __init__(							self						:   int	)					->		str:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						{}






     def     SCREAMING_SNAKE_CASE__  (							self						:   List[Any]	)					->		None:




           '''simple docstring'''


           print(self.vertex	)
           for i in self.vertex:
                 print(lowerCamelCase__						,""" -> """						,""" -> """.join([str(lowerCamelCase__	) for j in self.vertex[i]]	)	)






     def     SCREAMING_SNAKE_CASE__  (							self						:   List[Any]						,lowerCamelCase__						:   int						,lowerCamelCase__						:   int	)					->		None:




           '''simple docstring'''


           if from_vertex in self.vertex:
                 self.vertex[from_vertex].append(lowerCamelCase__	)
           else:
                 # else make a new vertex
                 SCREAMING_SNAKE_CASE		=						[to_vertex]






     def     SCREAMING_SNAKE_CASE__  (							self						:   str	)					->		None:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						[False] * len(self.vertex	)

           # call the recursive helper function
           for i in range(len(self.vertex	)	):
                 if not visited[i]:
                       self.dfs_recursive(lowerCamelCase__						,lowerCamelCase__	)






     def     SCREAMING_SNAKE_CASE__  (							self						:   Any						,lowerCamelCase__						:   int						,lowerCamelCase__						:   list	)					->		None:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						True

           print(lowerCamelCase__						,end=""" """	)

           # Recur for all the vertices that are adjacent to this node
           for i in self.vertex:
                 if not visited[i]:
                       self.dfs_recursive(lowerCamelCase__						,lowerCamelCase__	)


if __name__ == "__main__":
      SCREAMING_SNAKE_CASE_						       =	Graph()
      g.add_edge(0, 1)
      g.add_edge(0, 2)
      g.add_edge(1, 2)
      g.add_edge(2, 0)
      g.add_edge(2, 3)
      g.add_edge(3, 3)

      g.print_graph()
      print("""DFS:""")
      g.dfs()

      # OUTPUT:
      # 0  ->  1 -> 2
      # 1  ->  2
      # 2  ->  0 -> 3
      # 3  ->  3
      # DFS:
      #  0 1 2 3


