





import sys
from collections import defaultdict
class 			UpperCamelCase_		:




					def __init__(		self  )		->							Tuple:
												_snake_case									=				[]




					def 	lowerCAmelCase			(		self				,						lowerCAmelCase_  )		->							List[str]:
												return self.node_position[vertex]




					def 	lowerCAmelCase			(		self				,						lowerCAmelCase_				,						lowerCAmelCase_  )		->							Optional[int]:
												_snake_case									=				pos




					def 	lowerCAmelCase			(		self				,						lowerCAmelCase_				,						lowerCAmelCase_				,						lowerCAmelCase_				,						lowerCAmelCase_  )		->							List[Any]:
												if start > size // 2 - 1:
																			return
												else:
																			if 2 * start + 2 >= size:
																										_snake_case									=				2 * start + 1
																			else:
																										if heap[2 * start + 1] < heap[2 * start + 2]:
																																	_snake_case									=				2 * start + 1
																										else:
																																	_snake_case									=				2 * start + 2
																			if heap[smallest_child] < heap[start]:
																										_snake_case							,     _snake_case									=				heap[smallest_child], positions[smallest_child]
																										_snake_case							,     _snake_case									=				(
																										    heap[start],
																										    positions[start],
																										)
																										_snake_case							,     _snake_case									=				temp, tempa

																										_snake_case									=				self.get_position(positions[smallest_child]  )
																										self.set_position(
																										    positions[smallest_child]				,						self.get_position(positions[start]  )  )
																										self.set_position(positions[start]				,						snake_case_  )

																										self.top_to_bottom(snake_case_				,						snake_case_				,						snake_case_				,						snake_case_  )




					def 	lowerCAmelCase			(		self				,						lowerCAmelCase_				,						lowerCAmelCase_				,						lowerCAmelCase_				,						lowerCAmelCase_  )		->							Any:
												_snake_case									=				position[index]

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

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




					def 	lowerCAmelCase			(		self				,						lowerCAmelCase_				,						lowerCAmelCase_  )		->							Any:
												_snake_case									=				len(snake_case_  ) // 2 - 1
												for i in range(snake_case_				,						-1				,						-1  ):
																			self.top_to_bottom(snake_case_				,						snake_case_				,						len(snake_case_  )				,						snake_case_  )






					def 	lowerCAmelCase			(		self				,						lowerCAmelCase_				,						lowerCAmelCase_  )		->							List[Any]:
												_snake_case									=				positions[0]
												_snake_case									=				sys.maxsize
												self.top_to_bottom(snake_case_				,						0				,						len(snake_case_  )				,						snake_case_  )
												return temp





def 						lowerCamelCase__     (     UpperCamelCase__			:       Tuple						)			-> Tuple:



							'''simple docstring'''




							_snake_case									=				Heap()

							_snake_case									=				[0] * len(UpperCamelCase__						)
							_snake_case									=				[-1] * len(UpperCamelCase__						)  # Neighboring Tree Vertex of selected vertex
							# Minimum Distance of explored vertex with neighboring vertex of partial tree
							# formed in graph
							_snake_case									=				[]  # Heap of Distance of vertices from their neighboring vertex
							_snake_case									=				[]

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

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

							for _ in range(1       ,    len(UpperCamelCase__						)						):
														_snake_case									=				heap.delete_minimum(UpperCamelCase__       ,    UpperCamelCase__						)
														if visited[vertex] == 0:
																					tree_edges.append((nbr_tv[vertex], vertex)						)
																					_snake_case									=				1
																					for neighbor, distance in adjacency_list[vertex]:
																												if (
																												    visited[neighbor] == 0
																												    and distance < distance_tv[heap.get_position(UpperCamelCase__						)]
																												):
																																			_snake_case									=				distance
																																			heap.bottom_to_top(
																																			    UpperCamelCase__       ,    heap.get_position(UpperCamelCase__						)       ,    UpperCamelCase__       ,    UpperCamelCase__						)
																																			_snake_case									=				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))










def 						lowerCamelCase__     (     UpperCamelCase__			:       list[int]       ,    UpperCamelCase__			:       int						)			-> bool:



					'''simple docstring'''




					_snake_case									=				len(UpperCamelCase__						)
					_snake_case									=				[[False] * (required_sum + 1) for _ in range(arr_len + 1						)]

					# for each arr value, a sum of zero(0) can be formed by not taking any element
					# hence True/1
					for i in range(arr_len + 1						):
										_snake_case									=				True

					# sum is not zero and set is empty then false
					for i in range(1       ,    required_sum + 1						):
										_snake_case									=				False

					for i in range(1       ,    arr_len + 1						):
										for j in range(1       ,    required_sum + 1						):
															if arr[i - 1] > j:
																				_snake_case									=				subset[i - 1][j]
															if arr[i - 1] <= j:
																				_snake_case									=				subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]

					return subset[arr_len][required_sum]


if __name__ == "__main__":
					import doctest

					doctest.testmod()



