
"""simple docstring"""







from __future__ import annotations

import unittest
from collections.abc import Iterator




class 					A__			:

		def __init__( self			,						_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE					):
			__lowerCAmelCase     :		List[str]		     = label
			__lowerCAmelCase     :		str		     = parent
			__lowerCAmelCase     :		Node | None		     = None
			__lowerCAmelCase     :		Node | None		     = None




class 					A__			:

		def __init__( self					):
			__lowerCAmelCase     :		Node | None		     = None

		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		Tuple		     = None

		def 				__lowerCamelCase				( self					):
			return self.root is None

		def 				__lowerCamelCase				( self			,						_SCREAMING_SNAKE_CASE					):
			__lowerCAmelCase     :		List[str]		     = self._put(self.root			,						_SCREAMING_SNAKE_CASE					)

		def 				__lowerCamelCase				( self			,						_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE = None					):
			if node is None:
				__lowerCAmelCase     :		List[str]		     = Node(_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE					)
			else:
				if label < node.label:
					__lowerCAmelCase     :		Optional[int]		     = self._put(node.left			,						_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE					)
				elif label > node.label:
					__lowerCAmelCase     :		int		     = self._put(node.right			,						_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE					)
				else:
					__lowerCAmelCase     :		Optional[Any]		     = f"Node with label {label} already exists"
					raise Exception(_SCREAMING_SNAKE_CASE					)

			return node

		def 				__lowerCamelCase				( self			,						_SCREAMING_SNAKE_CASE					):
			return self._search(self.root			,						_SCREAMING_SNAKE_CASE					)

		def 				__lowerCamelCase				( self			,						_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE					):
			if node is None:
				__lowerCAmelCase     :		Optional[Any]		     = f"Node with label {label} does not exist"
				raise Exception(_SCREAMING_SNAKE_CASE					)
			else:
				if label < node.label:
					__lowerCAmelCase     :		List[str]		     = self._search(node.left			,						_SCREAMING_SNAKE_CASE					)
				elif label > node.label:
					__lowerCAmelCase     :		Optional[int]		     = self._search(node.right			,						_SCREAMING_SNAKE_CASE					)

			return node

		def 				__lowerCamelCase				( self			,						_SCREAMING_SNAKE_CASE					):
			__lowerCAmelCase     :		Dict		     = self.search(_SCREAMING_SNAKE_CASE					)
			if node.right and node.left:
				__lowerCAmelCase     :		Tuple		     = self._get_lowest_node(node.right					)
				__lowerCAmelCase     :		Any		     = node.left
				__lowerCAmelCase     :		Any		     = node.right
				__lowerCAmelCase     :		str		     = lowest_node
				if node.right:
					__lowerCAmelCase     :		Optional[int]		     = lowest_node
				self._reassign_nodes(_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE					)
			elif not node.right and node.left:
				self._reassign_nodes(_SCREAMING_SNAKE_CASE			,						node.left					)
			elif node.right and not node.left:
				self._reassign_nodes(_SCREAMING_SNAKE_CASE			,						node.right					)
			else:
				self._reassign_nodes(_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE					)

		def 				__lowerCamelCase				( self			,						_SCREAMING_SNAKE_CASE			,						_SCREAMING_SNAKE_CASE					):
			if new_children:
				__lowerCAmelCase     :		List[str]		     = node.parent

			if node.parent:
				if node.parent.right == node:
					__lowerCAmelCase     :		Optional[int]		     = new_children
				else:
					__lowerCAmelCase     :		Optional[Any]		     = new_children
			else:
				__lowerCAmelCase     :		Any		     = new_children

		def 				__lowerCamelCase				( self			,						_SCREAMING_SNAKE_CASE					):
			if node.left:
				__lowerCAmelCase     :		Optional[int]		     = self._get_lowest_node(node.left					)
			else:
				__lowerCAmelCase     :		Optional[Any]		     = node
				self._reassign_nodes(_SCREAMING_SNAKE_CASE			,						node.right					)

			return lowest_node

		def 				__lowerCamelCase				( self			,						_SCREAMING_SNAKE_CASE					):
			try:
				self.search(_SCREAMING_SNAKE_CASE					)
				return True
			except Exception:
				return False

		def 				__lowerCamelCase				( self					):
			if self.root is None:
				raise Exception('Binary search tree is empty'					)

			__lowerCAmelCase     :		int		     = self.root
			while node.right is not None:
				__lowerCAmelCase     :		Optional[Any]		     = node.right

			return node.label

		def 				__lowerCamelCase				( self					):
			if self.root is None:
				raise Exception('Binary search tree is empty'					)

			__lowerCAmelCase     :		Optional[int]		     = self.root
			while node.left is not None:
				__lowerCAmelCase     :		str		     = node.left

			return node.label

		def 				__lowerCamelCase				( self					):
			return self._inorder_traversal(self.root					)

		def 				__lowerCamelCase				( self			,						_SCREAMING_SNAKE_CASE					):
			if node is not None:
				yield from self._inorder_traversal(node.left					)
				yield node
				yield from self._inorder_traversal(node.right					)

		def 				__lowerCamelCase				( self					):
			return self._preorder_traversal(self.root					)







		def 				__lowerCamelCase				( self			,						_SCREAMING_SNAKE_CASE					):
			if node is not None:
				yield node
				yield from self._preorder_traversal(node.left					)
				yield from self._preorder_traversal(node.right					)




class 					A__			(      unittest.TestCase):

		@staticmethod
		def 				__lowerCamelCase				( ):
			__lowerCAmelCase     :		Optional[int]		     = BinarySearchTree()
			t.put(8					)
			t.put(3					)
			t.put(6					)
			t.put(1					)
			t.put(10					)
			t.put(14					)
			t.put(13					)
			t.put(4					)
			t.put(7					)
			t.put(5					)

			return t

		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		Dict		     = BinarySearchTree()
			assert t.is_empty()

			t.put(8					)
			assert t.root is not None
			assert t.root.parent is None
			assert t.root.label == 8

			t.put(10					)
			assert t.root.right is not None
			assert t.root.right.parent == t.root
			assert t.root.right.label == 10

			t.put(3					)
			assert t.root.left is not None
			assert t.root.left.parent == t.root
			assert t.root.left.label == 3

			t.put(6					)
			assert t.root.left.right is not None
			assert t.root.left.right.parent == t.root.left
			assert t.root.left.right.label == 6

			t.put(1					)
			assert t.root.left.left is not None
			assert t.root.left.left.parent == t.root.left
			assert t.root.left.left.label == 1

			with self.assertRaises(_SCREAMING_SNAKE_CASE					):  # noqa: B017
				t.put(1					)

		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		str		     = self._get_binary_search_tree()

			__lowerCAmelCase     :		Union[str, Any]		     = t.search(6					)
			assert node.label == 6

			__lowerCAmelCase     :		Union[str, Any]		     = t.search(13					)
			assert node.label == 13

			with self.assertRaises(_SCREAMING_SNAKE_CASE					):  # noqa: B017
				t.search(2					)

		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		str		     = self._get_binary_search_tree()

			t.remove(13					)
			assert t.root is not None
			assert t.root.right is not None
			assert t.root.right.right is not None
			assert t.root.right.right.right is None
			assert t.root.right.right.left is None

			t.remove(7					)
			assert t.root.left is not None
			assert t.root.left.right is not None
			assert t.root.left.right.left is not None
			assert t.root.left.right.right is None
			assert t.root.left.right.left.label == 4

			t.remove(6					)
			assert t.root.left.left is not None
			assert t.root.left.right.right is not None
			assert t.root.left.left.label == 1
			assert t.root.left.right.label == 4
			assert t.root.left.right.right.label == 5
			assert t.root.left.right.left is None
			assert t.root.left.left.parent == t.root.left
			assert t.root.left.right.parent == t.root.left

			t.remove(3					)
			assert t.root is not None
			assert t.root.left.label == 4
			assert t.root.left.right.label == 5
			assert t.root.left.left.label == 1
			assert t.root.left.parent == t.root
			assert t.root.left.left.parent == t.root.left
			assert t.root.left.right.parent == t.root.left

			t.remove(4					)
			assert t.root.left is not None
			assert t.root.left.left is not None
			assert t.root.left.label == 5
			assert t.root.left.right is None
			assert t.root.left.left.label == 1
			assert t.root.left.parent == t.root
			assert t.root.left.left.parent == t.root.left

		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		int		     = self._get_binary_search_tree()

			t.remove(3					)
			assert t.root is not None
			assert t.root.left is not None
			assert t.root.left.left is not None
			assert t.root.left.right is not None
			assert t.root.left.right.left is not None
			assert t.root.left.right.right is not None
			assert t.root.left.label == 4
			assert t.root.left.right.label == 6
			assert t.root.left.left.label == 1
			assert t.root.left.right.right.label == 7
			assert t.root.left.right.left.label == 5
			assert t.root.left.parent == t.root
			assert t.root.left.right.parent == t.root.left
			assert t.root.left.left.parent == t.root.left
			assert t.root.left.right.left.parent == t.root.left.right

		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		List[Any]		     = self._get_binary_search_tree()
			t.empty()
			assert t.root is None

		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		Any		     = self._get_binary_search_tree()
			assert not t.is_empty()

			t.empty()
			assert t.is_empty()

		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		Optional[int]		     = self._get_binary_search_tree()

			assert t.exists(6					)
			assert not t.exists(-1					)

		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		Union[str, Any]		     = self._get_binary_search_tree()

			assert t.get_max_label() == 14

			t.empty()
			with self.assertRaises(_SCREAMING_SNAKE_CASE					):  # noqa: B017
				t.get_max_label()

		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		Any		     = self._get_binary_search_tree()

			assert t.get_min_label() == 1

			t.empty()
			with self.assertRaises(_SCREAMING_SNAKE_CASE					):  # noqa: B017
				t.get_min_label()

		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		Optional[Any]		     = self._get_binary_search_tree()

			__lowerCAmelCase     :		Optional[int]		     = [i.label for i in t.inorder_traversal()]
			assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]







		def 				__lowerCamelCase				( self					):
			__lowerCAmelCase     :		List[Any]		     = self._get_binary_search_tree()

			__lowerCAmelCase     :		List[str]		     = [i.label for i in t.preorder_traversal()]
			assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]



def        __lowerCAmelCase							():
	__lowerCAmelCase     :		Union[str, Any]		     = BinarySearchTree()
	t.put(8						)
	t.put(3						)
	t.put(6						)
	t.put(1						)
	t.put(10						)
	t.put(14						)
	t.put(13						)
	t.put(4						)
	t.put(7						)
	t.put(5						)

	print(
	    '\n            8\n           / \\\n          3   10\n         / \\    \\\n        1   6    14\n           / \\   /\n          4   7 13\n           \\\n            5\n        '						)

	print('Label 6 exists:'			,    t.exists(6						)						)
	print('Label 13 exists:'			,    t.exists(13						)						)
	print('Label -1 exists:'			,    t.exists(-1						)						)
	print('Label 12 exists:'			,    t.exists(12						)						)

	# Prints all the elements of the list in inorder traversal
	__lowerCAmelCase     :		int		     = [i.label for i in t.inorder_traversal()]
	print('Inorder traversal:'			,    _UpperCamelCase						)

	# Prints all the elements of the list in preorder traversal
	__lowerCAmelCase     :		Tuple		     = [i.label for i in t.preorder_traversal()]
	print('Preorder traversal:'			,    _UpperCamelCase						)

	print('Max. label:'			,    t.get_max_label()						)
	print('Min. label:'			,    t.get_min_label()						)

	# Delete elements
	print('\nDeleting elements 13, 10, 8, 3, 6, 14'						)
	print(
	    '\n          4\n         / \\\n        1   7\n             \\\n              5\n        '						)
	t.remove(13						)
	t.remove(10						)
	t.remove(8						)
	t.remove(3						)
	t.remove(6						)
	t.remove(14						)

	# Prints all the elements of the list in inorder traversal after delete
	__lowerCAmelCase     :		str		     = [i.label for i in t.inorder_traversal()]
	print('Inorder traversal after delete:'			,    _UpperCamelCase						)

	# Prints all the elements of the list in preorder traversal after delete
	__lowerCAmelCase     :		Optional[int]		     = [i.label for i in t.preorder_traversal()]
	print('Preorder traversal after delete:'			,    _UpperCamelCase						)

	print('Max. label:'			,    t.get_max_label()						)
	print('Min. label:'			,    t.get_min_label()						)


if __name__ == "__main__":
							binary_search_tree_example()

"""simple docstring"""







def        __lowerCAmelCase							(_UpperCamelCase			,    _UpperCamelCase						):
	__lowerCAmelCase     :		Any		     = sorted(_UpperCamelCase			,    key=lambda _UpperCamelCase						: edge[2]						)

	__lowerCAmelCase     :		Union[str, Any]		     = list(range(_UpperCamelCase						)						)

	def find_parent(_UpperCamelCase						):
		if i != parent[i]:
			__lowerCAmelCase     :		int		     = find_parent(parent[i]						)
		return parent[i]

	__lowerCAmelCase     :		Optional[Any]		     = 0
	__lowerCAmelCase     :		List[str]		     = []

	for edge in edges:
		__lowerCAmelCase     :		List[str]		     = find_parent(edge[0]						)
		__lowerCAmelCase     :		Optional[Any]		     = find_parent(edge[1]						)
		if parent_a != parent_b:
			minimum_spanning_tree_cost += edge[2]
			minimum_spanning_tree.append(_UpperCamelCase						)
			__lowerCAmelCase     :		Optional[Any]		     = parent_b

	return minimum_spanning_tree


if __name__ == "__main__":  # pragma: no cover
							lowerCamelCase__   ,		lowerCamelCase__     =						list(map(int, input().strip().split()))
							lowerCamelCase__     =						[]

							for _ in range(num_edges):
														lowerCamelCase__   ,		lowerCamelCase__   ,		lowerCamelCase__     =						(int(x) for x in input().strip().split())
														edges.append((nodea, nodea, cost))

							kruskal(num_nodes, edges)