
'''simple docstring'''

import timeit
from typing import Callable, Optional

from ..configuration_utils import PretrainedConfig
from ..models.auto.modeling_auto import MODEL_MAPPING, MODEL_WITH_LM_HEAD_MAPPING
from ..utils import is_pyanvml_available, is_torch_available, logging
from .benchmark_utils import (
    Benchmark,
    Memory,
    MemorySummary,
    measure_peak_memory_cpu,
    start_memory_tracing,
    stop_memory_tracing,
)


if is_torch_available():
   import torch

   from .benchmark_args import PyTorchBenchmarkArguments


if is_pyanvml_available():
   import pyanvml.pyanvml as nvml


__UpperCAmelCase												=   logging.get_logger(__name__)


class 		_a     (							SCREAMING_SNAKE_CASE  ):







   """simple docstring"""




   A		= 42
   A		= 42
   A		= "PyTorch"






   @property
   def 					__a			(       self      ):
    return torch.__version__






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      ):
    SCREAMING_SNAKE_CASE  :  Optional[Any]								=		self._prepare_inference_func(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
    return self._measure_speed(_inference      )






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      ):
    SCREAMING_SNAKE_CASE  :  List[str]								=		self._prepare_inference_func(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
    return self._measure_memory(_inference      )






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      ):
    SCREAMING_SNAKE_CASE  :  str								=		self._prepare_train_func(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
    return self._measure_speed(_train      )






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      ):
    SCREAMING_SNAKE_CASE  :  str								=		self._prepare_train_func(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
    return self._measure_memory(_train      )






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      ):
    SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		self.config_dict[model_name]

    if self.args.torchscript:
     SCREAMING_SNAKE_CASE  :  Any								=		True

    SCREAMING_SNAKE_CASE  :  str								=		(
        hasattr(__SCREAMING_SNAKE_CASE    ,'architectures'      )
        and isinstance(config.architectures    ,__SCREAMING_SNAKE_CASE      )
        and len(config.architectures      ) > 0
    )
    if not self.args.only_pretrain_model and has_model_class_in_config:
     try:
      SCREAMING_SNAKE_CASE  :  Optional[int]								=		config.architectures[0]
      SCREAMING_SNAKE_CASE  :  Dict								=		__import__('transformers'    ,fromlist=[model_class]      )
      SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		getattr(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
      SCREAMING_SNAKE_CASE  :  Any								=		model_cls(__SCREAMING_SNAKE_CASE      )
     except ImportError:
      raise ImportError(
          f"""{model_class} does not exist. If you just want to test the pretrained model, you might want to"""
          ' set `--only_pretrain_model` or `args.only_pretrain_model=True`.'      )
    else:
     SCREAMING_SNAKE_CASE  :  Any								=		MODEL_MAPPING[config.__class__](__SCREAMING_SNAKE_CASE      )

    model.eval()
    model.to(self.args.device      )

    # encoder-decoder has vocab size saved differently
    SCREAMING_SNAKE_CASE  :  Optional[int]								=		config.vocab_size if hasattr(__SCREAMING_SNAKE_CASE    ,'vocab_size'      ) else config.encoder.vocab_size
    SCREAMING_SNAKE_CASE  :  List[str]								=		torch.randint(__SCREAMING_SNAKE_CASE    ,(batch_size, sequence_length)    ,dtype=torch.long    ,device=self.args.device      )

    if self.args.fpaa:
     logger.info('Running training in Mixed Precision...'      )
     if not self.args.is_gpu:
      raise ValueError('Mixed precision is possible only for GPU.'      )
     # amp seems to have memory leaks so that memory usage
     # is measured using .half() for now https://github.com/NVIDIA/apex/issues/439
     model.half()

    if self.args.torchscript:
     with torch.no_grad():
      SCREAMING_SNAKE_CASE  :  Dict								=		torch.jit.trace(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
    else:
     SCREAMING_SNAKE_CASE  :  Optional[int]								=		model

    def encoder_decoder_forward():
     with torch.no_grad():
      SCREAMING_SNAKE_CASE  :  str								=		inference_model(__SCREAMING_SNAKE_CASE    ,decoder_input_ids=__SCREAMING_SNAKE_CASE      )
     return outputs

    def encoder_forward():
     with torch.no_grad():
      SCREAMING_SNAKE_CASE  :  List[str]								=		inference_model(__SCREAMING_SNAKE_CASE      )
     return outputs

    SCREAMING_SNAKE_CASE  :  int								=		encoder_decoder_forward if config.is_encoder_decoder else encoder_forward
    return _forward






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      ):
    SCREAMING_SNAKE_CASE  :  Optional[Any]								=		self.config_dict[model_name]

    SCREAMING_SNAKE_CASE  :  int								=		(
        hasattr(__SCREAMING_SNAKE_CASE    ,'architectures'      )
        and isinstance(config.architectures    ,__SCREAMING_SNAKE_CASE      )
        and len(config.architectures      ) > 0
    )
    if not self.args.only_pretrain_model and has_model_class_in_config:
     try:
      SCREAMING_SNAKE_CASE  :  List[str]								=		config.architectures[0]
      SCREAMING_SNAKE_CASE  :  List[str]								=		__import__('transformers'    ,fromlist=[model_class]      )
      SCREAMING_SNAKE_CASE  :  Any								=		getattr(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
      SCREAMING_SNAKE_CASE  :  str								=		model_cls(__SCREAMING_SNAKE_CASE      )
     except ImportError:
      raise ImportError(
          f"""{model_class} does not exist. If you just want to test the pretrained model, you might want to"""
          ' set `--only_pretrain_model` or `args.only_pretrain_model=True`.'      )
    else:
     SCREAMING_SNAKE_CASE  :  Dict								=		MODEL_WITH_LM_HEAD_MAPPING[config.__class__](__SCREAMING_SNAKE_CASE      )

    if self.args.torchscript:
     raise NotImplementedError('Training for torchscript is currently not implemented'      )
    else:
     SCREAMING_SNAKE_CASE  :  Dict								=		model

    model.train()
    model.to(self.args.device      )

    # encoder-decoder has vocab size saved differently
    SCREAMING_SNAKE_CASE  :  Dict								=		config.vocab_size if hasattr(__SCREAMING_SNAKE_CASE    ,'vocab_size'      ) else config.encoder.vocab_size
    SCREAMING_SNAKE_CASE  :  List[Any]								=		torch.randint(__SCREAMING_SNAKE_CASE    ,(batch_size, sequence_length)    ,dtype=torch.long    ,device=self.args.device      )

    if self.args.fpaa:
     logger.info('Running training in Mixed Precision...'      )
     if not self.args.is_gpu:
      raise ValueError('Mixed precision is possible only for GPU.'      )

     # amp seems to have memory leaks so that memory usage
     # is measured using .half() for now https://github.com/NVIDIA/apex/issues/439
     model.half()

    def compute_loss_and_backprob_encoder():
     SCREAMING_SNAKE_CASE  :  List[Any]								=		train_model(__SCREAMING_SNAKE_CASE    ,labels=__SCREAMING_SNAKE_CASE      )[0]
     loss.backward()
     return loss

    def compute_loss_and_backprob_encoder_decoder():
     SCREAMING_SNAKE_CASE  :  Optional[int]								=		train_model(__SCREAMING_SNAKE_CASE    ,decoder_input_ids=__SCREAMING_SNAKE_CASE    ,labels=__SCREAMING_SNAKE_CASE      )[0]
     loss.backward()
     return loss

    SCREAMING_SNAKE_CASE  :  Optional[int]								=		(
        compute_loss_and_backprob_encoder_decoder
        if config.is_encoder_decoder
        else compute_loss_and_backprob_encoder
    )
    return _train






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE      ):
    try:
     if self.args.is_tpu or self.args.torchscript:
      # run additional 10 times to stabilize compilation for tpu and torchscript
      logger.info('Do inference on TPU or torchscript. Running model 5 times to stabilize compilation'      )
      timeit.repeat(
          __SCREAMING_SNAKE_CASE    ,repeat=1    ,number=5    ,)

     # as written in https://docs.python.org/2/library/timeit.html#timeit.Timer.repeat, min should be taken rather than the average
     SCREAMING_SNAKE_CASE  :  List[Any]								=		timeit.repeat(
         __SCREAMING_SNAKE_CASE    ,repeat=self.args.repeat    ,number=10    ,)

     if self.args.is_tpu and self.args.torch_xla_tpu_print_metrics:
      import torch_xla.debug.metrics as met

      self.print_fn(met.metrics_report()      )

     return min(__SCREAMING_SNAKE_CASE      ) / 10.0
    except RuntimeError as e:
     self.print_fn(f"""Doesn't fit on GPU. {e}"""      )
     return "N/A"






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE      ):
    try:
     if self.args.trace_memory_line_by_line:
      SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		start_memory_tracing('transformers'      )

     if self.args.is_tpu:
      # tpu
      raise NotImplementedError(
          'Memory Benchmarking is currently not implemented for TPU. Please disable memory benchmarking with'
          ' `--no-memory` or `args.memory=False`'      )
     elif self.args.is_gpu:
      if not is_pyanvml_available():
       logger.warning(
           'py3nvml not installed, we won\'t log GPU memory usage. '
           'Install py3nvml (pip install py3nvml) to log information about GPU.'      )
       SCREAMING_SNAKE_CASE  :  Optional[Any]								=		'N/A'
      else:
       logger.info(
           'Measuring total GPU usage on GPU device. Make sure to not have additional processes running'
           ' on the same GPU.'      )
       # init nvml
       nvml.nvmlInit()
       func()
       SCREAMING_SNAKE_CASE  :  Any								=		nvml.nvmlDeviceGetHandleByIndex(self.args.device_idx      )
       SCREAMING_SNAKE_CASE  :  Optional[Any]								=		nvml.nvmlDeviceGetMemoryInfo(__SCREAMING_SNAKE_CASE      )
       SCREAMING_SNAKE_CASE  :  Dict								=		meminfo.used
       SCREAMING_SNAKE_CASE  :  str								=		Memory(__SCREAMING_SNAKE_CASE      )
       # shutdown nvml
       nvml.nvmlShutdown()
     else:
      # cpu
      SCREAMING_SNAKE_CASE  :  List[Any]								=		measure_peak_memory_cpu(__SCREAMING_SNAKE_CASE      )
      SCREAMING_SNAKE_CASE  :  int								=		Memory(__SCREAMING_SNAKE_CASE      ) if isinstance(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      ) else memory_bytes

     if self.args.trace_memory_line_by_line:
      SCREAMING_SNAKE_CASE  :  int								=		stop_memory_tracing(__SCREAMING_SNAKE_CASE      )
     else:
      SCREAMING_SNAKE_CASE  :  str								=		None

     return memory, summary
    except RuntimeError as e:
     self.print_fn(f"""Doesn't fit on GPU. {e}"""      )
     return "N/A", None




'''simple docstring'''

def        SCREAMING_SNAKE_CASE_  (	snake_case_				:	int   ,     snake_case_				:	list[tuple[int, int, int]]							)       ->	list[tuple[int, int, int]]:
 SCREAMING_SNAKE_CASE  :  List[Any]								=		sorted(snake_case_   ,     key=lambda snake_case_							: edge[2]							)

 SCREAMING_SNAKE_CASE  :  str								=		list(range(snake_case_							)							)

 def find_parent(snake_case_				:	Union[str, Any]							):
  if i != parent[i]:
   SCREAMING_SNAKE_CASE  :  int								=		find_parent(parent[i]							)
  return parent[i]

 SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		0
 SCREAMING_SNAKE_CASE  :  Any								=		[]

 for edge in edges:
  SCREAMING_SNAKE_CASE  :  Dict								=		find_parent(edge[0]							)
  SCREAMING_SNAKE_CASE  :  Optional[int]								=		find_parent(edge[1]							)
  if parent_a != parent_b:
   minimum_spanning_tree_cost += edge[2]
   minimum_spanning_tree.append(snake_case_							)
   SCREAMING_SNAKE_CASE  :  Tuple								=		parent_b

 return minimum_spanning_tree


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

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

   kruskal(num_nodes, edges)


