




import sys
from collections import defaultdict



class       a_       :





	def __init__(							self      )  ->					Optional[Any]:




				"""simple docstring"""



				SCREAMING_SNAKE_CASE_								=						[]





	def 						A_(							self      ,     SCREAMING_SNAKE_CASE      )  ->					Tuple:




				"""simple docstring"""



				return self.node_position[vertex]





	def 						A_(							self      ,     SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      )  ->					Any:




				"""simple docstring"""



				SCREAMING_SNAKE_CASE_								=						pos





	def 						A_(							self      ,     SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      )  ->					Optional[Any]:




				"""simple docstring"""



				if start > size // 2 - 1:
							return
				else:
							if 2 * start + 2 >= size:
										SCREAMING_SNAKE_CASE_								=						2 * start + 1
							else:
										if heap[2 * start + 1] < heap[2 * start + 2]:
													SCREAMING_SNAKE_CASE_								=						2 * start + 1
										else:
													SCREAMING_SNAKE_CASE_								=						2 * start + 2
							if heap[smallest_child] < heap[start]:
										SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_								=						heap[smallest_child], positions[smallest_child]
										SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_								=						(
										    heap[start],
										    positions[start],
										)
										SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_								=						temp, tempa

										SCREAMING_SNAKE_CASE_								=						self.get_position(positions[smallest_child]      )
										self.set_position(
										    positions[smallest_child]      ,     self.get_position(positions[start]      )      )
										self.set_position(positions[start]      ,     SCREAMING_SNAKE_CASE      )

										self.top_to_bottom(SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      )





	def 						A_(							self      ,     SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      )  ->					Dict:




				"""simple docstring"""



				SCREAMING_SNAKE_CASE_								=						position[index]

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

							if val < heap[parent]:
										SCREAMING_SNAKE_CASE_								=						heap[parent]
										SCREAMING_SNAKE_CASE_								=						position[parent]
										self.set_position(position[parent]      ,     SCREAMING_SNAKE_CASE      )
							else:
										SCREAMING_SNAKE_CASE_								=						val
										SCREAMING_SNAKE_CASE_								=						temp
										self.set_position(SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      )
										break
							SCREAMING_SNAKE_CASE_								=						parent
				else:
							SCREAMING_SNAKE_CASE_								=						val
							SCREAMING_SNAKE_CASE_								=						temp
							self.set_position(SCREAMING_SNAKE_CASE      ,     0      )





	def 						A_(							self      ,     SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      )  ->					Dict:




				"""simple docstring"""



				SCREAMING_SNAKE_CASE_								=						len(SCREAMING_SNAKE_CASE      ) // 2 - 1
				for i in range(SCREAMING_SNAKE_CASE      ,     -1      ,     -1      ):
							self.top_to_bottom(SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      ,     len(SCREAMING_SNAKE_CASE      )      ,     SCREAMING_SNAKE_CASE      )





	def 						A_(							self      ,     SCREAMING_SNAKE_CASE      ,     SCREAMING_SNAKE_CASE      )  ->					Optional[int]:




				"""simple docstring"""



				SCREAMING_SNAKE_CASE_								=						positions[0]
				SCREAMING_SNAKE_CASE_								=						sys.maxsize
				self.top_to_bottom(SCREAMING_SNAKE_CASE      ,     0      ,     len(SCREAMING_SNAKE_CASE      )      ,     SCREAMING_SNAKE_CASE      )
				return temp




def lowercase    (  SCREAMING_SNAKE_CASE )			->							Optional[int]:


			'''simple docstring'''







			SCREAMING_SNAKE_CASE_								=						Heap()

			SCREAMING_SNAKE_CASE_								=						[0] * len(SCREAMING_SNAKE_CASE )
			SCREAMING_SNAKE_CASE_								=						[-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
			SCREAMING_SNAKE_CASE_								=						[]  # Heap of Distance of vertices from their neighboring vertex
			SCREAMING_SNAKE_CASE_								=						[]

			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 )

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

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


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






def lowercase    (  SCREAMING_SNAKE_CASE )			->							int:


			'''simple docstring'''







			if not numbers:
						return 0

			if not isinstance(SCREAMING_SNAKE_CASE       ,    (list, tuple) ) or not all(
			    isinstance(SCREAMING_SNAKE_CASE       ,    SCREAMING_SNAKE_CASE ) for number in numbers ):
						raise ValueError('numbers must be an iterable of integers' )

			SCREAMING_SNAKE_CASE_								=						SCREAMING_SNAKE_CASE_								=						SCREAMING_SNAKE_CASE_								=						numbers[0]

			for i in range(1       ,    len(SCREAMING_SNAKE_CASE ) ):
						# update the maximum and minimum subarray products
						SCREAMING_SNAKE_CASE_								=						numbers[i]
						if number < 0:
									SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_								=						min_till_now, max_till_now
						SCREAMING_SNAKE_CASE_								=						max(SCREAMING_SNAKE_CASE       ,    max_till_now * number )
						SCREAMING_SNAKE_CASE_								=						min(SCREAMING_SNAKE_CASE       ,    min_till_now * number )

						# update the maximum product found till now
						SCREAMING_SNAKE_CASE_								=						max(SCREAMING_SNAKE_CASE       ,    SCREAMING_SNAKE_CASE )

			return max_prod
