





import sys
from collections import defaultdict

class 		snake_case_   :







	'''simple docstring'''




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

			'''simple docstring'''




			__lowercase											=     []




	def    UpperCAmelCase			(						self							:     int					,      __lowerCamelCase							:     Optional[int]   )       -> List[str]:

			'''simple docstring'''




			return self.node_position[vertex]




	def    UpperCAmelCase			(						self							:     Optional[int]					,      __lowerCamelCase							:     int					,      __lowerCamelCase							:     Dict   )       -> Union[str, Any]:

			'''simple docstring'''




			__lowercase											=     pos




	def    UpperCAmelCase			(						self							:     Optional[Any]					,      __lowerCamelCase							:     int					,      __lowerCamelCase							:     List[str]					,      __lowerCamelCase							:     Dict					,      __lowerCamelCase							:     List[Any]   )       -> List[str]:

			'''simple docstring'''




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

							__lowercase											=     self.get_position(positions[smallest_child]   )
							self.set_position(
							    positions[smallest_child]					,      self.get_position(positions[start]   )   )
							self.set_position(positions[start]					,      __lowerCamelCase   )

							self.top_to_bottom(__lowerCamelCase					,      __lowerCamelCase					,      __lowerCamelCase					,      __lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     Optional[Any]					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     int					,      __lowerCamelCase							:     List[str]   )       -> List[Any]:

			'''simple docstring'''




			__lowercase											=     position[index]

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

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




	def    UpperCAmelCase			(						self							:     Optional[Any]					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     str   )       -> int:

			'''simple docstring'''




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






	def    UpperCAmelCase			(						self							:     Union[str, Any]					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     Union[str, Any]   )       -> Union[str, Any]:

			'''simple docstring'''




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





def  SCREAMING_SNAKE_CASE				(      snake_case							)		->    Any:
		__lowercase											=     Heap()

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

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

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

		for _ in range(1						,   len(snake_case							)							):
				__lowercase											=     heap.delete_minimum(snake_case						,   snake_case							)
				if visited[vertex] == 0:
						tree_edges.append((nbr_tv[vertex], vertex)							)
						__lowercase											=     1
						for neighbor, distance in adjacency_list[vertex]:
								if (
								    visited[neighbor] == 0
								    and distance < distance_tv[heap.get_position(snake_case							)]
								):
										__lowercase											=     distance
										heap.bottom_to_top(
										    snake_case						,   heap.get_position(snake_case							)						,   snake_case						,   snake_case							)
										__lowercase											=     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_   :      Optional[int]			=   defaultdict(list)
		for _ in range(edges_number):
				SCREAMING_SNAKE_CASE_   :      Union[str, 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))











from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

SCREAMING_SNAKE_CASE_   :      Optional[int]			=   TypeVar('''T''')



def  SCREAMING_SNAKE_CASE				(      snake_case							)		->    int:
		return (position - 1) // 2



def  SCREAMING_SNAKE_CASE				(      snake_case							)		->    int:
		return (2 * position) + 1



def  SCREAMING_SNAKE_CASE				(      snake_case							)		->    int:
		return (2 * position) + 2

class 		snake_case_   (							Generic[T]						):







	'''simple docstring'''




	def __init__(						self							:     Any   )       -> None:

			'''simple docstring'''




			__lowercase											=     []
			__lowercase											=     {}
			__lowercase											=     0




	def __len__(						self							:     Optional[Any]   )       -> int:

			'''simple docstring'''




			return self.elements




	def __repr__(						self							:     Optional[Any]   )       -> str:

			'''simple docstring'''




			return str(self.heap   )




	def    UpperCAmelCase			(						self							:     Union[str, Any]   )       -> bool:

			'''simple docstring'''




			return self.elements == 0




	def    UpperCAmelCase			(						self							:     str					,      __lowerCamelCase							:     T					,      __lowerCamelCase							:     int   )       -> None:

			'''simple docstring'''




			self.heap.append((elem, weight)   )
			__lowercase											=     self.elements
			self.elements += 1
			self._bubble_up(__lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     Dict   )       -> T:

			'''simple docstring'''




			if self.elements > 1:
					self._swap_nodes(0					,      self.elements - 1   )
			__lowercase						,      __lowercase											=     self.heap.pop()
			del self.position_map[elem]
			self.elements -= 1
			if self.elements > 0:
					__lowercase						,      __lowercase											=     self.heap[0]
					self._bubble_down(__lowerCamelCase   )
			return elem




	def    UpperCAmelCase			(						self							:     int					,      __lowerCamelCase							:     T					,      __lowerCamelCase							:     int   )       -> None:

			'''simple docstring'''




			__lowercase											=     self.position_map[elem]
			__lowercase											=     (elem, weight)
			if position > 0:
					__lowercase											=     get_parent_position(__lowerCamelCase   )
					__lowercase						,      __lowercase											=     self.heap[parent_position]
					if parent_weight > weight:
							self._bubble_up(__lowerCamelCase   )
					else:
							self._bubble_down(__lowerCamelCase   )
			else:
					self._bubble_down(__lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     Tuple					,      __lowerCamelCase							:     T   )       -> None:

			'''simple docstring'''




			__lowercase											=     self.position_map[elem]
			if curr_pos == 0:
					return None
			__lowercase											=     get_parent_position(__lowerCamelCase   )
			__lowercase						,      __lowercase											=     self.heap[curr_pos]
			__lowercase						,      __lowercase											=     self.heap[parent_position]
			if parent_weight > weight:
					self._swap_nodes(__lowerCamelCase					,      __lowerCamelCase   )
					return self._bubble_up(__lowerCamelCase   )
			return None




	def    UpperCAmelCase			(						self							:     List[str]					,      __lowerCamelCase							:     T   )       -> None:

			'''simple docstring'''




			__lowercase											=     self.position_map[elem]
			__lowercase						,      __lowercase											=     self.heap[curr_pos]
			__lowercase											=     get_child_left_position(__lowerCamelCase   )
			__lowercase											=     get_child_right_position(__lowerCamelCase   )
			if child_left_position < self.elements and child_right_position < self.elements:
					__lowercase						,      __lowercase											=     self.heap[child_left_position]
					__lowercase						,      __lowercase											=     self.heap[child_right_position]
					if child_right_weight < child_left_weight and child_right_weight < weight:
							self._swap_nodes(__lowerCamelCase					,      __lowerCamelCase   )
							return self._bubble_down(__lowerCamelCase   )
			if child_left_position < self.elements:
					__lowercase						,      __lowercase											=     self.heap[child_left_position]
					if child_left_weight < weight:
							self._swap_nodes(__lowerCamelCase					,      __lowerCamelCase   )
							return self._bubble_down(__lowerCamelCase   )
			else:
					return None
			if child_right_position < self.elements:
					__lowercase						,      __lowercase											=     self.heap[child_right_position]
					if child_right_weight < weight:
							self._swap_nodes(__lowerCamelCase					,      __lowerCamelCase   )
							return self._bubble_down(__lowerCamelCase   )
			return None






	def    UpperCAmelCase			(						self							:     Optional[int]					,      __lowerCamelCase							:     int					,      __lowerCamelCase							:     int   )       -> None:

			'''simple docstring'''




			__lowercase											=     self.heap[nodea_pos][0]
			__lowercase											=     self.heap[nodea_pos][0]
			__lowercase						,      __lowercase											=     (
			    self.heap[nodea_pos],
			    self.heap[nodea_pos],
			)
			__lowercase											=     nodea_pos
			__lowercase											=     nodea_pos





class 		snake_case_   (							Generic[T]						):







	'''simple docstring'''




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

			'''simple docstring'''




			__lowercase											=     {}
			__lowercase											=     0




	def __repr__(						self							:     Union[str, Any]   )       -> str:

			'''simple docstring'''




			return str(self.connections   )




	def __len__(						self							:     int   )       -> int:

			'''simple docstring'''




			return self.nodes




	def    UpperCAmelCase			(						self							:     Optional[int]					,      __lowerCamelCase							:     T   )       -> None:

			'''simple docstring'''




			if node not in self.connections:
					__lowercase											=     {}
					self.nodes += 1






	def    UpperCAmelCase			(						self							:     List[Any]					,      __lowerCamelCase							:     T					,      __lowerCamelCase							:     T					,      __lowerCamelCase							:     int   )       -> None:

			'''simple docstring'''




			self.add_node(__lowerCamelCase   )
			self.add_node(__lowerCamelCase   )
			__lowercase											=     weight
			__lowercase											=     weight





def  SCREAMING_SNAKE_CASE				(      snake_case						,   )		->    tuple[dict[T, int], dict[T, T | None]]:
		__lowercase											=     {node: maxsize for node in graph.connections}
		__lowercase											=     {node: None for node in graph.connections}

		__lowercase											=     MinPriorityQueue()
		for node, weight in dist.items():
				priority_queue.push(snake_case						,   snake_case							)

		if priority_queue.is_empty():
				return dist, parent

		# initialization
		__lowercase											=     priority_queue.extract_min()
		__lowercase											=     0
		for neighbour in graph.connections[node]:
				if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
						__lowercase											=     dist[node] + graph.connections[node][neighbour]
						priority_queue.update_key(snake_case						,   dist[neighbour]							)
						__lowercase											=     node

    # running prim's algorithm
		while not priority_queue.is_empty():
				__lowercase											=     priority_queue.extract_min()
				for neighbour in graph.connections[node]:
						if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
								__lowercase											=     dist[node] + graph.connections[node][neighbour]
								priority_queue.update_key(snake_case						,   dist[neighbour]							)
								__lowercase											=     node
		return dist, parent




