






import sys
from collections import defaultdict






class 					SCREAMING_SNAKE_CASE_  :
       """simple docstring"""


       def __init__(				self	:Optional[int]):



          """simple docstring"""

          _lowercase              =[]





       def 				UpperCamelCase__						(				self	:int,      snake_case	:int):



          """simple docstring"""

          return self.node_position[vertex]





       def 				UpperCamelCase__						(				self	:Optional[Any],      snake_case	:Optional[Any],      snake_case	:Tuple):



          """simple docstring"""

          _lowercase              =pos





       def 				UpperCamelCase__						(				self	:Tuple,      snake_case	:Optional[Any],      snake_case	:int,      snake_case	:List[Any],      snake_case	:Dict):



          """simple docstring"""

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

                _lowercase              =self.get_position(positions[smallest_child])
                self.set_position(
                    positions[smallest_child],      self.get_position(positions[start]))
                self.set_position(positions[start],      snake_case)

                self.top_to_bottom(snake_case,      snake_case,      snake_case,      snake_case)





       def 				UpperCamelCase__						(				self	:List[str],      snake_case	:List[Any],      snake_case	:Tuple,      snake_case	:Tuple,      snake_case	:Tuple):



          """simple docstring"""

          _lowercase              =position[index]

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

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





       def 				UpperCamelCase__						(				self	:Tuple,      snake_case	:Union[str, Any],      snake_case	:Dict):



          """simple docstring"""

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





       def 				UpperCamelCase__						(				self	:Any,      snake_case	:List[Any],      snake_case	:Dict):



          """simple docstring"""

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





def        _snake_case   (_snake_case				:       List[Any])					->	Any:
   _lowercase              =Heap()

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

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

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

   for _ in range(1      ,    len(_snake_case)):
      _lowercase              =heap.delete_minimum(_snake_case      ,    _snake_case)
      if visited[vertex] == 0:
         tree_edges.append((nbr_tv[vertex], vertex))
         _lowercase              =1
         for neighbor, distance in adjacency_list[vertex]:
            if (
                visited[neighbor] == 0
                and distance < distance_tv[heap.get_position(_snake_case)]
            ):
               _lowercase              =distance
               heap.bottom_to_top(
                   _snake_case      ,    heap.get_position(_snake_case)      ,    _snake_case      ,    _snake_case)
               _lowercase              =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))










# Author: OMKAR PATHAK, Nwachukwu Chidiebere

# Use a Python dictionary to construct the graph.
from __future__ import annotations

from pprint import pformat
from typing import Generic, TypeVar

_SCREAMING_SNAKE_CASE   =  TypeVar("T")






class 					SCREAMING_SNAKE_CASE_  (       Generic[T] ):
       """simple docstring"""


       def __init__(				self	:List[Any],      snake_case	:bool = True):



          """simple docstring"""

          _lowercase              ={}  # dictionary of lists
          _lowercase              =directed





       def 				UpperCamelCase__						(				self	:Optional[Any],      snake_case	:T,      snake_case	:T):



          """simple docstring"""

          if not self.directed:  # For undirected graphs
             # if both source vertex and destination vertex are both present in the
             # adjacency list, add destination vertex to source vertex list of adjacent
             # vertices and add source vertex to destination vertex list of adjacent
             # vertices.
             if source_vertex in self.adj_list and destination_vertex in self.adj_list:
                self.adj_list[source_vertex].append(snake_case)
                self.adj_list[destination_vertex].append(snake_case)
             # if only source vertex is present in adjacency list, add destination vertex
             # to source vertex list of adjacent vertices, then create a new vertex with
             # destination vertex as key and assign a list containing the source vertex
             # as it's first adjacent vertex.
             elif source_vertex in self.adj_list:
                self.adj_list[source_vertex].append(snake_case)
                _lowercase              =[source_vertex]
             # if only destination vertex is present in adjacency list, add source vertex
             # to destination vertex list of adjacent vertices, then create a new vertex
             # with source vertex as key and assign a list containing the source vertex
             # as it's first adjacent vertex.
             elif destination_vertex in self.adj_list:
                self.adj_list[destination_vertex].append(snake_case)
                _lowercase              =[destination_vertex]
             # if both source vertex and destination vertex are not present in adjacency
             # list, create a new vertex with source vertex as key and assign a list
             # containing the destination vertex as it's first adjacent vertex also
             # create a new vertex with destination vertex as key and assign a list
             # containing the source vertex as it's first adjacent vertex.
             else:
                _lowercase              =[destination_vertex]
                _lowercase              =[source_vertex]
          else:  # For directed graphs
             # if both source vertex and destination vertex are present in adjacency
             # list, add destination vertex to source vertex list of adjacent vertices.
             if source_vertex in self.adj_list and destination_vertex in self.adj_list:
                self.adj_list[source_vertex].append(snake_case)
             # if only source vertex is present in adjacency list, add destination
             # vertex to source vertex list of adjacent vertices and create a new vertex
             # with destination vertex as key, which has no adjacent vertex
             elif source_vertex in self.adj_list:
                self.adj_list[source_vertex].append(snake_case)
                _lowercase              =[]
             # if only destination vertex is present in adjacency list, create a new
             # vertex with source vertex as key and assign a list containing destination
             # vertex as first adjacent vertex
             elif destination_vertex in self.adj_list:
                _lowercase              =[destination_vertex]
             # if both source vertex and destination vertex are not present in adjacency
             # list, create a new vertex with source vertex as key and a list containing
             # destination vertex as it's first adjacent vertex. Then create a new vertex
             # with destination vertex as key, which has no adjacent vertex
             else:
                _lowercase              =[destination_vertex]
                _lowercase              =[]

          return self





       def __repr__(				self	:Optional[int]):



          """simple docstring"""

          return pformat(self.adj_list)


