


import sys
from collections import defaultdict






class   UpperCamelCase       :


   '''simple docstring'''







   def __init__(  self		):
        lowercase_							:List[Any]			     =							[]
   def 		UpperCamelCase	(  self ,				UpperCamelCase_		):
        return self.node_position[vertex]
   def 		UpperCamelCase	(  self ,				UpperCamelCase_ ,				UpperCamelCase_		):
        lowercase_							:Union[str, Any]			     =							pos
   def 		UpperCamelCase	(  self ,				UpperCamelCase_ ,				UpperCamelCase_ ,				UpperCamelCase_ ,				UpperCamelCase_		):



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

                  lowercase_							:int			     =							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_		):
        lowercase_							:Optional[Any]			     =							position[index]

        while index != 0:
             lowercase_							:List[Any]			     =							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] ,				__UpperCAmelCase		)
             else:
                  lowercase_							:List[str]			     =							val
                  lowercase_							:Union[str, Any]			     =							temp
                  self.set_position(__UpperCAmelCase ,				__UpperCAmelCase		)
                  break
             lowercase_							:Optional[Any]			     =							parent
        else:
             lowercase_							:Optional[Any]			     =							val
             lowercase_							:int			     =							temp
             self.set_position(__UpperCAmelCase ,				0		)
   def 		UpperCamelCase	(  self ,				UpperCamelCase_ ,				UpperCamelCase_		):
        lowercase_							:List[Any]			     =							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_		):
        lowercase_							:Tuple			     =							positions[0]
        lowercase_							:Tuple			     =							sys.maxsize
        self.top_to_bottom(__UpperCAmelCase ,				0 ,				len(__UpperCAmelCase		) ,				__UpperCAmelCase		)
        return temp




def      UpperCamelCase     (   _a		)       ->				List[Any]:
     '''simple docstring'''





     lowercase_							:Tuple			     =							Heap()

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

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

     lowercase_							:Optional[int]			     =							[]
     lowercase_							:Optional[Any]			     =							1
     lowercase_							:Dict			     =							sys.maxsize
     for neighbor, distance in adjacency_list[0]:
          lowercase_							:Optional[int]			     =							0
          lowercase_							:Tuple			     =							distance
     heap.heapify(__UpperCamelCase							,		__UpperCamelCase		)

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


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






import qiskit






def     SCREAMING_SNAKE_CASE(      __UpperCamelCase = 2 )	->						qiskit.result.counts.Counts:
				a__	:							Any      						= qubits

				# Using Aer's simulator
				a__	:							Dict      						= qiskit.Aer.get_backend("aer_simulator" )

				# Creating a Quantum Circuit acting on the q register
				a__	:							Dict      						= qiskit.QuantumCircuit(__UpperCamelCase	,				__UpperCamelCase )

				# Adding a H gate on qubit 0 (now q0 in superposition)
				circuit.h(0 )

				for i in range(1	,				__UpperCamelCase ):
								# Adding CX (CNOT) gate
								circuit.cx(i - 1	,				__UpperCamelCase )

				# Mapping the quantum measurement to the classical bits
				circuit.measure(list(range(__UpperCamelCase ) )	,				list(range(__UpperCamelCase ) ) )

				# Now measuring any one qubit would affect other qubits to collapse
				# their super position and have same state as the measured one.

				# Executing the circuit on the simulator
				a__	:							Any      						= qiskit.execute(__UpperCamelCase	,				__UpperCamelCase	,				shots=10_00 )

				return job.result().get_counts(__UpperCamelCase )


if __name__ == "__main__":
						print(F'Total count for various states are: {quantum_entanglement(3)}')


