





import sys
from collections import defaultdict




class     SCREAMING_SNAKE_CASE__ :



 def __init__(							self ):
        A__											=						[]



 def 				UpperCamelCase			(							self,__lowerCamelCase ):
        return self.node_position[vertex]



 def 				UpperCamelCase			(							self,__lowerCamelCase,__lowerCamelCase ):
        A__											=						pos



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

                      A__											=						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 				UpperCamelCase			(							self,__lowerCamelCase,__lowerCamelCase,__lowerCamelCase,__lowerCamelCase ):
        A__											=						position[index]

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

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



 def 				UpperCamelCase			(							self,__lowerCamelCase,__lowerCamelCase ):
        A__											=						len(__lowerCamelCase ) // 2 - 1
        for i in range(__lowerCamelCase,-1,-1 ):
               self.top_to_bottom(__lowerCamelCase,__lowerCamelCase,len(__lowerCamelCase ),__lowerCamelCase )




 def 				UpperCamelCase			(							self,__lowerCamelCase,__lowerCamelCase ):
        A__											=						positions[0]
        A__											=						sys.maxsize
        self.top_to_bottom(__lowerCamelCase,0,len(__lowerCamelCase ),__lowerCamelCase )
        return temp


def 	UpperCamelCase__(       UpperCamelCase__			:       int  )->Optional[Any]:
       A__											=						Heap()

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

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

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

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


if __name__ == "__main__":  # pragma: no cover
       # < --------- Prims Algorithm --------- >
       a__:      Any									=		int(input('Enter number of edges: ').strip())
       a__:      int									=		defaultdict(list)
       for _ in range(edges_number):
              a__:      Union[str, Any]									=		[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))












from ..utils import DummyObject, requires_backends




class     SCREAMING_SNAKE_CASE__ (						metaclass=UpperCamelCase__      ):
 __SCREAMING_SNAKE_CASE							       =	['''keras_nlp''']



 def __init__(							self,*__lowerCamelCase,**__lowerCamelCase ):
        requires_backends(self,['''keras_nlp'''] )





