





'''simple docstring'''






import sys
from collections import defaultdict







class 		UpperCAmelCase   :


		"""simple docstring"""







		def __init__(				self    :					List[Any]  )     ->						List[str]:
				_UpperCamelCase       			=[]


		def   UpperCamelCase__      (				self    :					Tuple							,	UpperCamelCase__    :					str  )     ->						Dict:
				return self.node_position[vertex]


		def   UpperCamelCase__      (				self    :					str							,	UpperCamelCase__    :					Dict							,	UpperCamelCase__    :					Optional[Any]  )     ->						List[str]:
				_UpperCamelCase       			=pos


		def   UpperCamelCase__      (				self    :					int							,	UpperCamelCase__    :					Optional[int]							,	UpperCamelCase__    :					Dict							,	UpperCamelCase__    :					List[Any]							,	UpperCamelCase__    :					Optional[Any]  )     ->						List[Any]:






				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]							,	__lowerCAmelCase  )

								self.top_to_bottom(__lowerCAmelCase							,	__lowerCAmelCase							,	__lowerCAmelCase							,	__lowerCAmelCase  )


		def   UpperCamelCase__      (				self    :					Optional[int]							,	UpperCamelCase__    :					str							,	UpperCamelCase__    :					str							,	UpperCamelCase__    :					Any							,	UpperCamelCase__    :					str  )     ->						List[str]:
				_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]							,	__lowerCAmelCase  )
						else:
								_UpperCamelCase       			=val
								_UpperCamelCase       			=temp
								self.set_position(__lowerCAmelCase							,	__lowerCAmelCase  )
								break
						_UpperCamelCase       			=parent
				else:
						_UpperCamelCase       			=val
						_UpperCamelCase       			=temp
						self.set_position(__lowerCAmelCase							,	0  )


		def   UpperCamelCase__      (				self    :					Optional[int]							,	UpperCamelCase__    :					int							,	UpperCamelCase__    :					Tuple  )     ->						int:
				_UpperCamelCase       			=len(__lowerCAmelCase  ) // 2 - 1
				for i in range(__lowerCAmelCase							,	-1							,	-1  ):
						self.top_to_bottom(__lowerCAmelCase							,	__lowerCAmelCase							,	len(__lowerCAmelCase  )							,	__lowerCAmelCase  )




		def   UpperCamelCase__      (				self    :					Any							,	UpperCamelCase__    :					Optional[Any]							,	UpperCamelCase__    :					Any  )     ->						str:
				_UpperCamelCase       			=positions[0]
				_UpperCamelCase       			=sys.maxsize
				self.top_to_bottom(__lowerCAmelCase							,	0							,	len(__lowerCAmelCase  )							,	__lowerCAmelCase  )
				return temp




def 					_a   (__SCREAMING_SNAKE_CASE   ):


		"""simple docstring"""

		_UpperCamelCase       			=Heap()

		_UpperCamelCase       			=[0] * len(UpperCAmelCase__   )
		_UpperCamelCase       			=[-1] * len(UpperCAmelCase__   )  # 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(UpperCAmelCase__   )   ):
				distance_tv.append(sys.maxsize   )
				positions.append(UpperCAmelCase__   )
				heap.node_position.append(UpperCAmelCase__   )

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

		for _ in range(1  ,      len(UpperCAmelCase__   )   ):
				_UpperCamelCase       			=heap.delete_minimum(UpperCAmelCase__  ,      UpperCAmelCase__   )
				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(UpperCAmelCase__   )]
								):
										_UpperCamelCase       			=distance
										heap.bottom_to_top(
										    UpperCAmelCase__  ,      heap.get_position(UpperCAmelCase__   )  ,      UpperCAmelCase__  ,      UpperCAmelCase__   )
										_UpperCamelCase       			=vertex
		return tree_edges


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






import contextlib
from multiprocessing import Pool, RLock

from tqdm.auto import tqdm

from ..utils import experimental, logging


__lowerCamelCase						: Union[str, Any]		=   logging.get_logger(__name__)







class 		UpperCAmelCase   :


  """simple docstring"""







  lowerCAmelCase_					=				None




@experimental
def 					_a   (__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   ):


  """simple docstring"""

  if ParallelBackendConfig.backend_name is None:
    return _map_with_multiprocessing_pool(
        __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   )

  return _map_with_joblib(__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   )


def 					_a   (__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   ):


  """simple docstring"""

  _UpperCamelCase       			=num_proc if num_proc <= len(__SCREAMING_SNAKE_CASE   ) else len(__SCREAMING_SNAKE_CASE   )
  _UpperCamelCase       			=[]  # We organize the splits ourselve (contiguous splits)
  for index in range(__SCREAMING_SNAKE_CASE   ):
    _UpperCamelCase       			=len(__SCREAMING_SNAKE_CASE   ) // num_proc
    _UpperCamelCase       			=len(__SCREAMING_SNAKE_CASE   ) % num_proc
    _UpperCamelCase       			=div * index + min(__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   )
    _UpperCamelCase       			=start + div + (1 if index < mod else 0)
    split_kwds.append((function, iterable[start:end], types, index, disable_tqdm, desc)   )

  if len(__SCREAMING_SNAKE_CASE   ) != sum(len(i[1]   ) for i in split_kwds   ):
    raise ValueError(
        f'''Error dividing inputs iterable among processes. '''
        f'''Total number of objects {len(__SCREAMING_SNAKE_CASE   )}, '''
        f'''length: {sum(len(i[1]   ) for i in split_kwds   )}'''   )

  logger.info(
      f'''Spawning {num_proc} processes for {len(__SCREAMING_SNAKE_CASE   )} objects in slices of {[len(i[1]   ) for i in split_kwds]}'''   )
  _UpperCamelCase			,     _UpperCamelCase       			=None, None
  if not disable_tqdm:
    _UpperCamelCase			,     _UpperCamelCase       			=(RLock(),), tqdm.set_lock
  with Pool(__SCREAMING_SNAKE_CASE  ,      initargs=__SCREAMING_SNAKE_CASE  ,      initializer=__SCREAMING_SNAKE_CASE   ) as pool:
    _UpperCamelCase       			=pool.map(__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   )
  logger.info(f'''Finished {num_proc} processes'''   )
  _UpperCamelCase       			=[obj for proc_res in mapped for obj in proc_res]
  logger.info(f'''Unpacked {len(__SCREAMING_SNAKE_CASE   )} objects'''   )

  return mapped


def 					_a   (__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   ):


  """simple docstring"""

  import joblib

  with joblib.parallel_backend(ParallelBackendConfig.backend_name  ,      n_jobs=__SCREAMING_SNAKE_CASE   ):
    return joblib.Parallel()(
        joblib.delayed(__SCREAMING_SNAKE_CASE   )((function, obj, types, None, True, None)   ) for obj in iterable   )


@experimental
@contextlib.contextmanager
def 					_a   (__SCREAMING_SNAKE_CASE   ):


  """simple docstring"""

  _UpperCamelCase       			=backend_name

  if backend_name == "spark":
    from joblibspark import register_spark

    register_spark()

    # TODO: call create_cache_and_write_probe if "download" in steps
    # TODO: raise NotImplementedError when Dataset.map etc is called

  try:
    yield
  finally:
    _UpperCamelCase       			=None






