import sys
from collections import defaultdict





class UpperCAmelCase						:


				'''simple docstring'''






				def __init__(						self ):



						"""simple docstring"""





						A_		:    Optional[int]         =				[]
				def   lowerCAmelCase_       (						self		,     lowercase ):



						"""simple docstring"""





						return self.node_position[vertex]
				def   lowerCAmelCase_       (						self		,     lowercase		,     lowercase ):



						"""simple docstring"""





						A_		:    Any         =				pos
				def   lowerCAmelCase_       (						self		,     lowercase		,     lowercase		,     lowercase		,     lowercase ):



						"""simple docstring"""





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

										A_		:    List[str]         =				self.get_position(positions[smallest_child] )
										self.set_position(
										    positions[smallest_child]		,     self.get_position(positions[start] ) )
										self.set_position(positions[start]		,     lowercase )

										self.top_to_bottom(lowercase		,     lowercase		,     lowercase		,     lowercase )
				def   lowerCAmelCase_       (						self		,     lowercase		,     lowercase		,     lowercase		,     lowercase ):



						"""simple docstring"""





						A_		:    List[Any]         =				position[index]

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

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



						"""simple docstring"""





						A_		:    str         =				len(lowercase ) // 2 - 1
						for i in range(lowercase		,     -1		,     -1 ):
								self.top_to_bottom(lowercase		,     lowercase		,     len(lowercase )		,     lowercase )







				def   lowerCAmelCase_       (						self		,     lowercase		,     lowercase ):



						"""simple docstring"""





						A_		:    int         =				positions[0]
						A_		:    str         =				sys.maxsize
						self.top_to_bottom(lowercase		,     0		,     len(lowercase )		,     lowercase )
						return temp




def     UpperCamelCase						(	__lowercase						:			Any     ):
		'''simple docstring'''




		A_		:    Dict         =				Heap()

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

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

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

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


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







from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available, is_vision_available


_UpperCAmelCase            =		{
    """configuration_bridgetower""": [
        """BRIDGETOWER_PRETRAINED_CONFIG_ARCHIVE_MAP""",
        """BridgeTowerConfig""",
        """BridgeTowerTextConfig""",
        """BridgeTowerVisionConfig""",
    ],
    """processing_bridgetower""": ["""BridgeTowerProcessor"""],
}

try:
	if not is_vision_available():
		raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
	pass
else:
	_UpperCAmelCase            =		["""BridgeTowerImageProcessor"""]

try:
	if not is_torch_available():
		raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
	pass
else:
	_UpperCAmelCase            =		[
	    """BRIDGETOWER_PRETRAINED_MODEL_ARCHIVE_LIST""",
	    """BridgeTowerForContrastiveLearning""",
	    """BridgeTowerForImageAndTextRetrieval""",
	    """BridgeTowerForMaskedLM""",
	    """BridgeTowerModel""",
	    """BridgeTowerPreTrainedModel""",
	]


if TYPE_CHECKING:
	from .configuration_bridgetower import (
	    BRIDGETOWER_PRETRAINED_CONFIG_ARCHIVE_MAP,
	    BridgeTowerConfig,
	    BridgeTowerTextConfig,
	    BridgeTowerVisionConfig,
	)
	from .processing_bridgetower import BridgeTowerProcessor

	try:
		if not is_vision_available():
			raise OptionalDependencyNotAvailable()
	except OptionalDependencyNotAvailable:
		pass
	else:
		from .image_processing_bridgetower import BridgeTowerImageProcessor

	try:
		if not is_torch_available():
			raise OptionalDependencyNotAvailable()
	except OptionalDependencyNotAvailable:
		pass
	else:
		from .modeling_bridgetower import (
		    BRIDGETOWER_PRETRAINED_MODEL_ARCHIVE_LIST,
		    BridgeTowerForContrastiveLearning,
		    BridgeTowerForImageAndTextRetrieval,
		    BridgeTowerForMaskedLM,
		    BridgeTowerModel,
		    BridgeTowerPreTrainedModel,
		)


else:
	import sys

	_UpperCAmelCase            =		_LazyModule(__name__, globals()["""__file__"""], _import_structure)






