




"""simple docstring"""


import sys
from collections import defaultdict






class       lowercase:







 '''simple docstring'''





 def __init__(       self:	Optional[Any]	):




   '''simple docstring'''



   _snake_case							:	Any			=						[]


 def 				UpperCamelCase_     (       self:	List[Any],   a_:	Any	):




   '''simple docstring'''



   return self.node_position[vertex]


 def 				UpperCamelCase_     (       self:	Any,   a_:	List[Any],   a_:	str	):




   '''simple docstring'''



   _snake_case							:	Optional[Any]			=						pos


 def 				UpperCamelCase_     (       self:	List[Any],   a_:	int,   a_:	Dict,   a_:	int,   a_:	Optional[Any]	):




   '''simple docstring'''



   if start > size // 2 - 1:
     return
   else:
     if 2 * start + 2 >= size:
       _snake_case							:	Dict			=						2 * start + 1
     else:
       if heap[2 * start + 1] < heap[2 * start + 2]:
         _snake_case							:	int			=						2 * start + 1
       else:
         _snake_case							:	Optional[Any]			=						2 * start + 2
     if heap[smallest_child] < heap[start]:
       _snake_case	,      _snake_case							:	Any			=						heap[smallest_child], positions[smallest_child]
       _snake_case	,      _snake_case							:	Tuple			=						(
           heap[start],
           positions[start],
       )
       _snake_case	,      _snake_case							:	Optional[Any]			=						temp, tempa

       _snake_case							:	Dict			=						self.get_position(positions[smallest_child]	)
       self.set_position(
           positions[smallest_child],   self.get_position(positions[start]	)	)
       self.set_position(positions[start],   a_	)

       self.top_to_bottom(a_,   a_,   a_,   a_	)


 def 				UpperCamelCase_     (       self:	Union[str, Any],   a_:	List[Any],   a_:	Optional[Any],   a_:	Optional[int],   a_:	Dict	):




   '''simple docstring'''



   _snake_case							:	str			=						position[index]

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

     if val < heap[parent]:
       _snake_case							:	Union[str, Any]			=						heap[parent]
       _snake_case							:	int			=						position[parent]
       self.set_position(position[parent],   a_	)
     else:
       _snake_case							:	List[Any]			=						val
       _snake_case							:	Any			=						temp
       self.set_position(a_,   a_	)
       break
     _snake_case							:	int			=						parent
   else:
     _snake_case							:	Tuple			=						val
     _snake_case							:	List[Any]			=						temp
     self.set_position(a_,   0	)


 def 				UpperCamelCase_     (       self:	Optional[Any],   a_:	Optional[int],   a_:	int	):




   '''simple docstring'''



   _snake_case							:	Any			=						len(a_	) // 2 - 1
   for i in range(a_,   -1,   -1	):
     self.top_to_bottom(a_,   a_,   len(a_	),   a_	)


 def 				UpperCamelCase_     (       self:	Optional[Any],   a_:	List[str],   a_:	Union[str, Any]	):




   '''simple docstring'''



   _snake_case							:	List[Any]			=						positions[0]
   _snake_case							:	str			=						sys.maxsize
   self.top_to_bottom(a_,   0,   len(a_	),   a_	)
   return temp







def       UpperCAmelCase__ (snake_case__							:      str					):
  """simple docstring"""

  _snake_case							:	Optional[Any]			=						Heap()

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

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

  _snake_case							:	Any			=						[]
  _snake_case							:	Tuple			=						1
  _snake_case							:	List[str]			=						sys.maxsize
  for neighbor, distance in adjacency_list[0]:
    _snake_case							:	List[Any]			=						0
    _snake_case							:	Dict			=						distance
  heap.heapify(snake_case__	,     snake_case__					)

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


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








"""simple docstring"""


def       UpperCAmelCase__ (snake_case__							:      int					):
  """simple docstring"""

  if not isinstance(snake_case__	,     snake_case__					) or number < 0:
    raise ValueError("""Input must be a non-negative integer"""					)

  _snake_case							:	Dict			=						0
  while number:
    # This way we arrive at next set bit (next 1) instead of looping
    # through each bit and checking for 1s hence the
    # loop won't run 32 times it will only run the number of `1` times
    number &= number - 1
    count += 1
  return count


if __name__ == "__main__":
     import doctest

     doctest.testmod()


