from __future__ import annotations
class     lowerCAmelCase_     :







							def __init__(   self      :     Optional[Any] ,			_A      :     list[list[int]]		):
												_UpperCamelCase			     =     TypeError(
												    '''Matrices must be formed from a list of zero or more lists containing at '''
												    '''least one and the same number of values, each of which must be of type '''
												    '''int or float.'''		)
												if len(_A		) != 0:
																	_UpperCamelCase			     =     len(rows[0]		)
																	if cols == 0:
																						raise error
																	for row in rows:
																						if len(_A		) != cols:
																											raise error
																						for value in row:
																											if not isinstance(_A ,			(int, float)		):
																																raise error
																	_UpperCamelCase			     =     rows
												else:
																	_UpperCamelCase			     =     []







							def  UpperCamelCase_						(   self      :     Optional[Any]		):
												return [[row[i] for row in self.rows] for i in range(len(self.rows[0]		)		)]







							@property
							def  UpperCamelCase_						(   self      :     List[Any]		):
												return len(self.rows		)







							@property
							def  UpperCamelCase_						(   self      :     List[Any]		):
												return len(self.rows[0]		)







							@property
							def  UpperCamelCase_						(   self      :     Optional[Any]		):
												return (self.num_rows, self.num_columns)







							@property
							def  UpperCamelCase_						(   self      :     Tuple		):
												return self.order[0] == self.order[1]







							def  UpperCamelCase_						(   self      :     Dict		):
												_UpperCamelCase			     =     [
												    [0 if column_num != row_num else 1 for column_num in range(self.num_rows		)]
												    for row_num in range(self.num_rows		)
												]
												return Matrix(_A		)







							def  UpperCamelCase_						(   self      :     List[str]		):
												if not self.is_square:
																	return 0
												if self.order == (0, 0):
																	return 1
												if self.order == (1, 1):
																	return int(self.rows[0][0]		)
												if self.order == (2, 2):
																	return int(
																	    (self.rows[0][0] * self.rows[1][1])
																	    - (self.rows[0][1] * self.rows[1][0])		)
												else:
																	return sum(
																	    self.rows[0][column] * self.cofactors().rows[0][column]
																	    for column in range(self.num_columns		)		)







							def  UpperCamelCase_						(   self      :     Optional[Any]		):
												return bool(self.determinant()		)







							def  UpperCamelCase_						(   self      :     str ,			_A      :     int ,			_A      :     int		):
												_UpperCamelCase			     =     [
												    [
												        self.rows[other_row][other_column]
												        for other_column in range(self.num_columns		)
												        if other_column != column
												    ]
												    for other_row in range(self.num_rows		)
												    if other_row != row
												]
												return Matrix(_A		).determinant()







							def  UpperCamelCase_						(   self      :     Optional[int] ,			_A      :     int ,			_A      :     int		):
												if (row + column) % 2 == 0:
																	return self.get_minor(_A ,			_A		)
												return -1 * self.get_minor(_A ,			_A		)







							def  UpperCamelCase_						(   self      :     List[str]		):
												return Matrix(
												    [
												        [self.get_minor(_A ,			_A		) for column in range(self.num_columns		)]
												        for row in range(self.num_rows		)
												    ]		)







							def  UpperCamelCase_						(   self      :     Optional[int]		):
												return Matrix(
												    [
												        [
												            self.minors().rows[row][column]
												            if (row + column) % 2 == 0
												            else self.minors().rows[row][column] * -1
												            for column in range(self.minors().num_columns		)
												        ]
												        for row in range(self.minors().num_rows		)
												    ]		)







							def  UpperCamelCase_						(   self      :     Optional[int]		):
												_UpperCamelCase			     =     [
												    [self.cofactors().rows[column][row] for column in range(self.num_columns		)]
												    for row in range(self.num_rows		)
												]
												return Matrix(_A		)







							def  UpperCamelCase_						(   self      :     Tuple		):
												_UpperCamelCase			     =     self.determinant()
												if not determinant:
																	raise TypeError('''Only matrices with a non-zero determinant have an inverse'''		)
												return self.adjugate() * (1 / determinant)







							def __repr__(   self      :     List[Any]		):
												return str(self.rows		)







							def __str__(   self      :     List[Any]		):
												if self.num_rows == 0:
																	return "[]"
												if self.num_rows == 1:
																	return "[[" + ". ".join(str(self.rows[0]		)		) + "]]"
												return (
												    "["
												    + "\n ".join(
												        [
												            '''[''' + '''. '''.join([str(_A		) for value in row]		) + '''.]'''
												            for row in self.rows
												        ]		)
												    + "]"
												)







							def  UpperCamelCase_						(   self      :     List[str] ,			_A      :     list[int] ,			_A      :     int | None = None		):
												_UpperCamelCase			     =     TypeError('''Row must be a list containing all ints and/or floats'''		)
												if not isinstance(_A ,			_A		):
																	raise type_error
												for value in row:
																	if not isinstance(_A ,			(int, float)		):
																						raise type_error
												if len(_A		) != self.num_columns:
																	raise ValueError(
																	    '''Row must be equal in length to the other rows in the matrix'''		)
												if position is None:
																	self.rows.append(_A		)
												else:
																	_UpperCamelCase			     =     self.rows[0:position] + [row] + self.rows[position:]







							def  UpperCamelCase_						(   self      :     Optional[int] ,			_A      :     list[int] ,			_A      :     int | None = None		):
												_UpperCamelCase			     =     TypeError(
												    '''Column must be a list containing all ints and/or floats'''		)
												if not isinstance(_A ,			_A		):
																	raise type_error
												for value in column:
																	if not isinstance(_A ,			(int, float)		):
																						raise type_error
												if len(_A		) != self.num_rows:
																	raise ValueError(
																	    '''Column must be equal in length to the other columns in the matrix'''		)
												if position is None:
																	_UpperCamelCase			     =     [self.rows[i] + [column[i]] for i in range(self.num_rows		)]
												else:
																	_UpperCamelCase			     =     [
																	    self.rows[i][0:position] + [column[i]] + self.rows[i][position:]
																	    for i in range(self.num_rows		)
																	]







							def __eq__(   self      :     List[Any] ,			_A      :     object		):
												if not isinstance(_A ,			_A		):
																	return NotImplemented
												return self.rows == other.rows







							def __ne__(   self      :     List[str] ,			_A      :     object		):
												return not self == other







							def __neg__(   self      :     Any		):
												return self * -1







							def __add__(   self      :     Union[str, Any] ,			_A      :     Matrix		):
												if self.order != other.order:
																	raise ValueError('''Addition requires matrices of the same order'''		)
												return Matrix(
												    [
												        [self.rows[i][j] + other.rows[i][j] for j in range(self.num_columns		)]
												        for i in range(self.num_rows		)
												    ]		)







							def __sub__(   self      :     Union[str, Any] ,			_A      :     Matrix		):
												if self.order != other.order:
																	raise ValueError('''Subtraction requires matrices of the same order'''		)
												return Matrix(
												    [
												        [self.rows[i][j] - other.rows[i][j] for j in range(self.num_columns		)]
												        for i in range(self.num_rows		)
												    ]		)







							def __mul__(   self      :     Tuple ,			_A      :     Matrix | int | float		):
												if isinstance(_A ,			(int, float)		):
																	return Matrix(
																	    [[int(element * other		) for element in row] for row in self.rows]		)
												elif isinstance(_A ,			_A		):
																	if self.num_columns != other.num_rows:
																						raise ValueError(
																						    '''The number of columns in the first matrix must '''
																						    '''be equal to the number of rows in the second'''		)
																	return Matrix(
																	    [
																	        [Matrix.dot_product(_A ,			_A		) for column in other.columns()]
																	        for row in self.rows
																	    ]		)
												else:
																	raise TypeError(
																	    '''A Matrix can only be multiplied by an int, float, or another matrix'''		)







							def __pow__(   self      :     List[Any] ,			_A      :     int		):
												if not isinstance(_A ,			_A		):
																	raise TypeError('''A Matrix can only be raised to the power of an int'''		)
												if not self.is_square:
																	raise ValueError('''Only square matrices can be raised to a power'''		)
												if other == 0:
																	return self.identity()
												if other < 0:
																	if self.is_invertable():
																						return self.inverse() ** (-other)
																	raise ValueError(
																	    '''Only invertable matrices can be raised to a negative power'''		)
												_UpperCamelCase			     =     self
												for _ in range(other - 1		):
																	result *= self
												return result







							@classmethod
							def  UpperCamelCase_						(   cls      :     Union[str, Any] ,			_A      :     list[int] ,			_A      :     list[int]		):
												return sum(row[i] * column[i] for i in range(len(_A		)		)		)


if __name__ == "__main__":
					import doctest

					doctest.testmod()

import sys
from collections import defaultdict
class     lowerCAmelCase_     :







							def __init__(   self      :     Optional[int]		):
												_UpperCamelCase			     =     []







							def  UpperCamelCase_						(   self      :     Any ,			_A      :     str		):
												return self.node_position[vertex]







							def  UpperCamelCase_						(   self      :     Optional[Any] ,			_A      :     List[str] ,			_A      :     Union[str, Any]		):
												_UpperCamelCase			     =     pos







							def  UpperCamelCase_						(   self      :     Any ,			_A      :     List[str] ,			_A      :     int ,			_A      :     Optional[Any] ,			_A      :     Union[str, Any]		):
												if start > size // 2 - 1:
																	return
												else:
																	if 2 * start + 2 >= size:
																						_UpperCamelCase			     =     2 * start + 1
																	else:
																						if heap[2 * start + 1] < heap[2 * start + 2]:
																											_UpperCamelCase			     =     2 * start + 1
																						else:
																											_UpperCamelCase			     =     2 * start + 2
																	if heap[smallest_child] < heap[start]:
																						_UpperCamelCase     ,    _UpperCamelCase			     =     heap[smallest_child], positions[smallest_child]
																						_UpperCamelCase     ,    _UpperCamelCase			     =     (
																						    heap[start],
																						    positions[start],
																						)
																						_UpperCamelCase     ,    _UpperCamelCase			     =     temp, tempa

																						_UpperCamelCase			     =     self.get_position(positions[smallest_child]		)
																						self.set_position(
																						    positions[smallest_child] ,			self.get_position(positions[start]		)		)
																						self.set_position(positions[start] ,			_A		)

																						self.top_to_bottom(_A ,			_A ,			_A ,			_A		)







							def  UpperCamelCase_						(   self      :     List[str] ,			_A      :     Tuple ,			_A      :     Optional[Any] ,			_A      :     int ,			_A      :     Optional[int]		):
												_UpperCamelCase			     =     position[index]

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

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







							def  UpperCamelCase_						(   self      :     int ,			_A      :     Tuple ,			_A      :     int		):
												_UpperCamelCase			     =     len(_A		) // 2 - 1
												for i in range(_A ,			-1 ,			-1		):
																	self.top_to_bottom(_A ,			_A ,			len(_A		) ,			_A		)







							def  UpperCamelCase_						(   self      :     Any ,			_A      :     int ,			_A      :     List[str]		):
												_UpperCamelCase			     =     positions[0]
												_UpperCamelCase			     =     sys.maxsize
												self.top_to_bottom(_A ,			0 ,			len(_A		) ,			_A		)
												return temp




def 					_snake_case	(  __snake_case						):
					_UpperCamelCase			     =     Heap()

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

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

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

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


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