




'''simple docstring'''


import math
import time

from transformers import Trainer, is_torch_tpu_available
from transformers.trainer_utils import PredictionOutput, speed_metrics


if is_torch_tpu_available(check_device=False):
				import torch_xla.core.xla_model as xm
				import torch_xla.debug.metrics as met

class     A					(	_a					):







							def __init__(						self :						Union[str, Any]							,    *lowerCAmelCase_ :						List[Any]							,    lowerCAmelCase_ :						List[str]=None							,    lowerCAmelCase_ :						List[str]=None							,    **lowerCAmelCase_ :						Union[str, Any]      )    ->							Tuple:


														"""simple docstring"""


														super().__init__(*lowerCAmelCase_							,    **lowerCAmelCase_      )
														_a			  =       eval_examples
														_a			  =       post_process_function







							def      __lowerCAmelCase    (						self :						str							,    lowerCAmelCase_ :						List[str]=None							,    lowerCAmelCase_ :						Union[str, Any]=None							,    lowerCAmelCase_ :						List[str]=None							,    lowerCAmelCase_ :						str = "eval"      )    ->							Optional[int]:


														"""simple docstring"""


														_a			  =       self.eval_dataset if eval_dataset is None else eval_dataset
														_a			  =       self.get_eval_dataloader(lowerCAmelCase_      )
														_a			  =       self.eval_examples if eval_examples is None else eval_examples

														# Temporarily disable metric computation, we will do it in the loop here.
														_a			  =       self.compute_metrics
														_a			  =       None
														_a			  =       self.prediction_loop if self.args.use_legacy_prediction_loop else self.evaluation_loop
														_a			  =       time.time()
														try:
																					_a			  =       eval_loop(
																					    lowerCAmelCase_							,    description='''Evaluation'''							,    prediction_loss_only=True if compute_metrics is None else None							,    ignore_keys=lowerCAmelCase_							,    metric_key_prefix=lowerCAmelCase_							,    )
														finally:
																					_a			  =       compute_metrics
														_a			  =       self.args.eval_batch_size * self.args.world_size
														if F'{metric_key_prefix}_jit_compilation_time' in output.metrics:
																					start_time += output.metrics[F'{metric_key_prefix}_jit_compilation_time']
														output.metrics.update(
														    speed_metrics(
														        lowerCAmelCase_							,    lowerCAmelCase_							,    num_samples=output.num_samples							,    num_steps=math.ceil(output.num_samples / total_batch_size      )							,    )      )
														if self.post_process_function is not None and self.compute_metrics is not None and self.args.should_save:
																					# Only the main node write the results by default
																					_a			  =       self.post_process_function(lowerCAmelCase_							,    lowerCAmelCase_							,    output.predictions      )
																					_a			  =       self.compute_metrics(lowerCAmelCase_      )

																					# Prefix all keys with metric_key_prefix + '_'
																					for key in list(metrics.keys()      ):
																												if not key.startswith(F'{metric_key_prefix}_'      ):
																																			_a			  =       metrics.pop(lowerCAmelCase_      )
																					metrics.update(output.metrics      )
														else:
																					_a			  =       output.metrics

														if self.args.should_log:
																					# Only the main node log the results by default
																					self.log(lowerCAmelCase_      )

														if self.args.tpu_metrics_debug or self.args.debug:
																					# tpu-comment: Logging debug metrics for PyTorch/XLA (compile, execute times, ops, etc.)
																					xm.master_print(met.metrics_report()      )

														_a			  =       self.callback_handler.on_evaluate(self.args							,    self.state							,    self.control							,    lowerCAmelCase_      )
														return metrics







							def      __lowerCAmelCase    (						self :						Tuple							,    lowerCAmelCase_ :						Any							,    lowerCAmelCase_ :						Optional[Any]							,    lowerCAmelCase_ :						str=None							,    lowerCAmelCase_ :						str = "test"      )    ->							Union[str, Any]:


														"""simple docstring"""


														_a			  =       self.get_test_dataloader(lowerCAmelCase_      )

														# Temporarily disable metric computation, we will do it in the loop here.
														_a			  =       self.compute_metrics
														_a			  =       None
														_a			  =       self.prediction_loop if self.args.use_legacy_prediction_loop else self.evaluation_loop
														_a			  =       time.time()
														try:
																					_a			  =       eval_loop(
																					    lowerCAmelCase_							,    description='''Prediction'''							,    prediction_loss_only=True if compute_metrics is None else None							,    ignore_keys=lowerCAmelCase_							,    metric_key_prefix=lowerCAmelCase_							,    )
														finally:
																					_a			  =       compute_metrics
														_a			  =       self.args.eval_batch_size * self.args.world_size
														if F'{metric_key_prefix}_jit_compilation_time' in output.metrics:
																					start_time += output.metrics[F'{metric_key_prefix}_jit_compilation_time']
														output.metrics.update(
														    speed_metrics(
														        lowerCAmelCase_							,    lowerCAmelCase_							,    num_samples=output.num_samples							,    num_steps=math.ceil(output.num_samples / total_batch_size      )							,    )      )

														if self.post_process_function is None or self.compute_metrics is None:
																					return output

														_a			  =       self.post_process_function(lowerCAmelCase_							,    lowerCAmelCase_							,    output.predictions							,    '''predict'''      )
														_a			  =       self.compute_metrics(lowerCAmelCase_      )

														# Prefix all keys with metric_key_prefix + '_'
														for key in list(metrics.keys()      ):
																					if not key.startswith(F'{metric_key_prefix}_'      ):
																												_a			  =       metrics.pop(lowerCAmelCase_      )
														metrics.update(output.metrics      )
														return PredictionOutput(predictions=predictions.predictions							,    label_ids=predictions.label_ids							,    metrics=lowerCAmelCase_      )







'''simple docstring'''


import sys
from collections import defaultdict

class     A					:







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


														"""simple docstring"""


														_a			  =       []







							def      __lowerCAmelCase    (						self :						Union[str, Any]							,    lowerCAmelCase_ :						List[Any]      )    ->							int:


														"""simple docstring"""


														return self.node_position[vertex]







							def      __lowerCAmelCase    (						self :						List[Any]							,    lowerCAmelCase_ :						Optional[Any]							,    lowerCAmelCase_ :						Optional[Any]      )    ->							Tuple:


														"""simple docstring"""


														_a			  =       pos







							def      __lowerCAmelCase    (						self :						Dict							,    lowerCAmelCase_ :						str							,    lowerCAmelCase_ :						Any							,    lowerCAmelCase_ :						Dict							,    lowerCAmelCase_ :						int      )    ->							Any:


														"""simple docstring"""


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

																												_a			  =       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      __lowerCAmelCase    (						self :						Optional[int]							,    lowerCAmelCase_ :						List[str]							,    lowerCAmelCase_ :						List[Any]							,    lowerCAmelCase_ :						Any							,    lowerCAmelCase_ :						Dict      )    ->							Any:


														"""simple docstring"""


														_a			  =       position[index]

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

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







							def      __lowerCAmelCase    (						self :						Any							,    lowerCAmelCase_ :						List[Any]							,    lowerCAmelCase_ :						Optional[Any]      )    ->							Optional[int]:


														"""simple docstring"""


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







							def      __lowerCAmelCase    (						self :						str							,    lowerCAmelCase_ :						str							,    lowerCAmelCase_ :						int      )    ->							List[Any]:


														"""simple docstring"""


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



def 	snake_case_					(UpperCamelCase :						Any   ):





							'''simple docstring'''


							_a			  =       Heap()

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

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

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

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


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

