





'''simple docstring'''






import sys
from collections import defaultdict







class 		UpperCAmelCase   :


		"""simple docstring"""







		def __init__(				self    :					Dict  )     ->						Optional[int]:
				_UpperCamelCase       			=[]


		def   UpperCamelCase__      (				self    :					Optional[int]							,	UpperCamelCase__    :					Optional[Any]  )     ->						List[Any]:
				return self.node_position[vertex]


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


		def   UpperCamelCase__      (				self    :					Tuple							,	UpperCamelCase__    :					Dict							,	UpperCamelCase__    :					Dict							,	UpperCamelCase__    :					List[Any]							,	UpperCamelCase__    :					Optional[Any]  )     ->						int:
				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    :					Optional[Any]							,	UpperCamelCase__    :					Tuple							,	UpperCamelCase__    :					List[str]							,	UpperCamelCase__    :					Optional[Any]							,	UpperCamelCase__    :					Dict  )     ->						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]							,	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    :					Optional[Any]							,	UpperCamelCase__    :					str							,	UpperCamelCase__    :					Dict  )     ->						Optional[int]:
				_UpperCamelCase       			=len(UpperCamelCase__  ) // 2 - 1
				for i in range(UpperCamelCase__							,	-1							,	-1  ):
						self.top_to_bottom(UpperCamelCase__							,	UpperCamelCase__							,	len(UpperCamelCase__  )							,	UpperCamelCase__  )




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




def 					_a   (__SCREAMING_SNAKE_CASE   ):


		"""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 --------- >
						__lowerCamelCase						: List[str]		=   int(input('Enter number of edges: ').strip())
						__lowerCamelCase						: str		=   defaultdict(list)
						for _ in range(edges_number):
												__lowerCamelCase						: Dict		=   [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'''






# Copyright 2023 The HuggingFace Team. All rights reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


__lowerCamelCase						: Optional[int]		=   {
    'configuration_xmod': [
        'XMOD_PRETRAINED_CONFIG_ARCHIVE_MAP',
        'XmodConfig',
        'XmodOnnxConfig',
    ],
}

try:
      if not is_torch_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __lowerCamelCase						: int		=   [
          'XMOD_PRETRAINED_MODEL_ARCHIVE_LIST',
          'XmodForCausalLM',
          'XmodForMaskedLM',
          'XmodForMultipleChoice',
          'XmodForQuestionAnswering',
          'XmodForSequenceClassification',
          'XmodForTokenClassification',
          'XmodModel',
          'XmodPreTrainedModel',
      ]

if TYPE_CHECKING:
      from .configuration_xmod import XMOD_PRETRAINED_CONFIG_ARCHIVE_MAP, XmodConfig, XmodOnnxConfig

      try:
            if not is_torch_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .modeling_xmod import (
                XMOD_PRETRAINED_MODEL_ARCHIVE_LIST,
                XmodForCausalLM,
                XmodForMaskedLM,
                XmodForMultipleChoice,
                XmodForQuestionAnswering,
                XmodForSequenceClassification,
                XmodForTokenClassification,
                XmodModel,
                XmodPreTrainedModel,
            )

else:
      import sys

      __lowerCamelCase						: Dict		=   _LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)






