


import sys
from collections import defaultdict






class     UpperCamelCase:


					def __init__(						self	:		Tuple						)			->	Tuple:




											'''simple docstring'''

											__snake_case				=		[]


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Dict     ,    SCREAMING_SNAKE_CASE	:		List[Any]						)			->	List[Any]:




											'''simple docstring'''

											return self.node_position[vertex]


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[Any]     ,    SCREAMING_SNAKE_CASE	:		str     ,    SCREAMING_SNAKE_CASE	:		List[Any]						)			->	Optional[int]:




											'''simple docstring'''

											__snake_case				=		pos


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Dict     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]     ,    SCREAMING_SNAKE_CASE	:		Dict     ,    SCREAMING_SNAKE_CASE	:		str						)			->	Tuple:




											'''simple docstring'''

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

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Tuple     ,    SCREAMING_SNAKE_CASE	:		Optional[Any]     ,    SCREAMING_SNAKE_CASE	:		Optional[int]     ,    SCREAMING_SNAKE_CASE	:		Tuple     ,    SCREAMING_SNAKE_CASE	:		str						)			->	Tuple:




											'''simple docstring'''

											__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]     ,    SCREAMING_SNAKE_CASE						)
																	else:
																							__snake_case				=		val
																							__snake_case				=		temp
																							self.set_position(SCREAMING_SNAKE_CASE     ,    SCREAMING_SNAKE_CASE						)
																							break
																	__snake_case				=		parent
											else:
																	__snake_case				=		val
																	__snake_case				=		temp
																	self.set_position(SCREAMING_SNAKE_CASE     ,    0						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[Any]     ,    SCREAMING_SNAKE_CASE	:		str     ,    SCREAMING_SNAKE_CASE	:		List[str]						)			->	Dict:




											'''simple docstring'''

											__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 							SCREAMING_SNAKE_CASE_  (						self	:		Tuple     ,    SCREAMING_SNAKE_CASE	:		Optional[int]     ,    SCREAMING_SNAKE_CASE	:		List[Any]						)			->	Dict:




											'''simple docstring'''

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





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	int:


						'''simple docstring'''






						__snake_case				=		Heap()

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

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

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


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









import itertools
import string
from collections.abc import Generator, Iterable





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	Generator[tuple[str, ...], None, None]:


						'''simple docstring'''






						__snake_case				=		iter(_lowerCAmelCase )
						while True:
												__snake_case				=		tuple(itertools.islice(_lowerCAmelCase      ,	_lowerCAmelCase ) )
												if not chunk:
																		return
												yield chunk





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	str:


						'''simple docstring'''






						__snake_case				=		"".join([c.upper() for c in dirty if c in string.ascii_letters] )
						__snake_case				=		""

						if len(_lowerCAmelCase ) < 2:
												return dirty

						for i in range(len(_lowerCAmelCase ) - 1 ):
												clean += dirty[i]

												if dirty[i] == dirty[i + 1]:
																		clean += "X"

						clean += dirty[-1]

						if len(_lowerCAmelCase ) & 1:
												clean += "X"

						return clean





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	list[str]:


						'''simple docstring'''






						__snake_case				=		"ABCDEFGHIKLMNOPQRSTUVWXYZ"
						# we're using a list instead of a '2d' array because it makes the math
						# for setting up the table and doing the actual encoding/decoding simpler
						__snake_case				=		[]

						# copy key chars into the table if they are in `alphabet` ignoring duplicates
						for char in key.upper():
												if char not in table and char in alphabet:
																		table.append(_lowerCAmelCase )

    # fill the rest of the table in with the remaining alphabet chars
						for char in alphabet:
												if char not in table:
																		table.append(_lowerCAmelCase )

						return table





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	str:


						'''simple docstring'''






						__snake_case				=		generate_table(_lowerCAmelCase )
						__snake_case				=		prepare_input(_lowerCAmelCase )
						__snake_case				=		""

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(_lowerCAmelCase      ,	2 ):
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )

												if rowa == rowa:
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
												elif cola == cola:
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
												else:  # rectangle
																		ciphertext += table[rowa * 5 + cola]
																		ciphertext += table[rowa * 5 + cola]

						return ciphertext





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	str:


						'''simple docstring'''






						__snake_case				=		generate_table(_lowerCAmelCase )
						__snake_case				=		""

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(_lowerCAmelCase      ,	2 ):
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )

												if rowa == rowa:
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
												elif cola == cola:
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
												else:  # rectangle
																		plaintext += table[rowa * 5 + cola]
																		plaintext += table[rowa * 5 + cola]

						return plaintext





