





import sys
from collections import defaultdict




class 			__UpperCamelCase    :





     def __init__(     self					):
        _UpperCAmelCase           =   []





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





     def 		UpperCamelCase(     self				,							_UpperCamelCase				,							_UpperCamelCase					):
        _UpperCAmelCase           =   pos





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

              _UpperCAmelCase           =   self.get_position(positions[smallest_child]					)
              self.set_position(
                  positions[smallest_child]				,							self.get_position(positions[start]					)					)
              self.set_position(positions[start]				,							_UpperCamelCase					)

              self.top_to_bottom(_UpperCamelCase				,							_UpperCamelCase				,							_UpperCamelCase				,							_UpperCamelCase					)





     def 		UpperCamelCase(     self				,							_UpperCamelCase				,							_UpperCamelCase				,							_UpperCamelCase				,							_UpperCamelCase					):
        _UpperCAmelCase           =   position[index]

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

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





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





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




def      A__       (    SCREAMING_SNAKE_CASE_   :      Dict						)  ->  Dict:






   """simple docstring"""







   _UpperCAmelCase           =   Heap()

   _UpperCAmelCase           =   [0] * len(SCREAMING_SNAKE_CASE_						)
   _UpperCAmelCase           =   [-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
   _UpperCAmelCase           =   []  # Heap of Distance of vertices from their neighboring vertex
   _UpperCAmelCase           =   []

   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_						)

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

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


if __name__ == "__main__":  # pragma: no cover
   # < --------- Prims Algorithm --------- >
   UpperCAmelCase_           =	int(input("Enter number of edges: ").strip())
   UpperCAmelCase_           =	defaultdict(list)
   for _ in range(edges_number):
      UpperCAmelCase_           =	[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 typing import List

from .keymap import KEYMAP, get_character
def      A__       (    SCREAMING_SNAKE_CASE_   :      str						)  ->  List[str]:






   """simple docstring"""







   def decorator(SCREAMING_SNAKE_CASE_   :      List[Any]						):
      _UpperCAmelCase           =   getattr(SCREAMING_SNAKE_CASE_				,	'''handle_key'''				,	[]						)
      handle += [key]
      setattr(SCREAMING_SNAKE_CASE_				,	'''handle_key'''				,	SCREAMING_SNAKE_CASE_						)
      return func

   return decorator
def      A__       (    *SCREAMING_SNAKE_CASE_   :      List[str]						)  ->  Dict:






   """simple docstring"""







   def decorator(SCREAMING_SNAKE_CASE_   :      Any						):
      _UpperCAmelCase           =   getattr(SCREAMING_SNAKE_CASE_				,	'''handle_key'''				,	[]						)
      handle += keys
      setattr(SCREAMING_SNAKE_CASE_				,	'''handle_key'''				,	SCREAMING_SNAKE_CASE_						)
      return func

   return decorator




class 			__UpperCamelCase    (							A__    ):





     def __new__(     cls				,							_UpperCamelCase				,							_UpperCamelCase				,							_UpperCamelCase					):
        _UpperCAmelCase           =   super().__new__(cls				,							_UpperCamelCase				,							_UpperCamelCase				,							_UpperCamelCase					)
        if not hasattr(_UpperCamelCase				,							'''key_handler'''					):
           setattr(_UpperCamelCase				,							'''key_handler'''				,							{}					)
        setattr(_UpperCamelCase				,							'''handle_input'''				,							KeyHandler.handle_input					)

        for value in attrs.values():
           _UpperCAmelCase           =   getattr(_UpperCamelCase				,							'''handle_key'''				,							[]					)
           for key in handled_keys:
              _UpperCAmelCase           =   value
        return new_cls





     @staticmethod
     def 		UpperCamelCase(     cls					):
        _UpperCAmelCase           =   get_character()
        if char != KEYMAP["undefined"]:
           _UpperCAmelCase           =   ord(_UpperCamelCase					)
        _UpperCAmelCase           =   cls.key_handler.get(_UpperCamelCase					)
        if handler:
           _UpperCAmelCase           =   char
           return handler(cls					)
        else:
           return None




def      A__       (    cls   :      Union[str, Any]						)  ->  Any:






   """simple docstring"""







   return KeyHandler(cls.__name__				,	cls.__bases__				,	cls.__dict__.copy()						)