




import sys
from collections import defaultdict




class    __lowerCAmelCase       :






       def __init__(   self:					Optional[Any]				):
         lowercase    :Any      	=						[]






       def 					SCREAMING_SNAKE_CASE    (   self:					List[Any]       ,					_lowerCAmelCase:					Any				):
         return self.node_position[vertex]






       def 					SCREAMING_SNAKE_CASE    (   self:					Any       ,					_lowerCAmelCase:					List[Any]       ,					_lowerCAmelCase:					str				):
         lowercase    :Optional[Any]      	=						pos






       def 					SCREAMING_SNAKE_CASE    (   self:					List[Any]       ,					_lowerCAmelCase:					int       ,					_lowerCAmelCase:					Dict       ,					_lowerCAmelCase:					int       ,					_lowerCAmelCase:					Optional[Any]				):



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

             lowercase    :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 					SCREAMING_SNAKE_CASE    (   self:					Union[str, Any]       ,					_lowerCAmelCase:					List[Any]       ,					_lowerCAmelCase:					Optional[Any]       ,					_lowerCAmelCase:					Optional[int]       ,					_lowerCAmelCase:					Dict				):
         lowercase    :str      	=						position[index]

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

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






       def 					SCREAMING_SNAKE_CASE    (   self:					Optional[Any]       ,					_lowerCAmelCase:					Optional[int]       ,					_lowerCAmelCase:					int				):
         lowercase    :Any      	=						len(a_				) // 2 - 1
         for i in range(a_       ,					-1       ,					-1				):
           self.top_to_bottom(a_       ,					a_       ,					len(a_				)       ,					a_				)






       def 					SCREAMING_SNAKE_CASE    (   self:					Optional[Any]       ,					_lowerCAmelCase:					List[str]       ,					_lowerCAmelCase:					Union[str, Any]				):
         lowercase    :List[Any]      	=						positions[0]
         lowercase    :str      	=						sys.maxsize
         self.top_to_bottom(a_       ,					0       ,					len(a_				)       ,					a_				)
         return temp







def       UpperCAmelCase__  (     lowerCamelCase   ):
  lowercase    :Optional[Any]      	=						Heap()

  lowercase    :Optional[Any]      	=						[0] * len(snake_case__   )
  lowercase    :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
  lowercase    :List[str]      	=						[]  # Heap of Distance of vertices from their neighboring vertex
  lowercase    :Dict      	=						[]

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

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

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


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









def       UpperCAmelCase__  (     lowerCamelCase,			lowerCamelCase   ):
  return int((input_a, input_a).count(0   ) != 0   )



def       UpperCAmelCase__  (     ):
  assert nand_gate(0,			0   ) == 1
  assert nand_gate(0,			1   ) == 1
  assert nand_gate(1,			0   ) == 1
  assert nand_gate(1,			1   ) == 0


if __name__ == "__main__":
     print(nand_gate(0, 0))
     print(nand_gate(0, 1))
     print(nand_gate(1, 0))
     print(nand_gate(1, 1))



