
'''simple docstring'''

from __future__ import annotations

import copy
import os
import tempfile
from importlib import import_module
from math import isnan

from transformers import is_tf_available
from transformers.models.auto import get_values
from transformers.testing_utils import _tf_gpu_memory_limit, require_tf, slow

from ..test_modeling_tf_common import ids_tensor


if is_tf_available():
   import numpy as np
   import tensorflow as tf

   from transformers import (
       TF_MODEL_FOR_CAUSAL_LM_MAPPING,
       TF_MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING,
       TF_MODEL_FOR_MASKED_LM_MAPPING,
       TF_MODEL_FOR_MULTIPLE_CHOICE_MAPPING,
       TF_MODEL_FOR_NEXT_SENTENCE_PREDICTION_MAPPING,
       TF_MODEL_FOR_PRETRAINING_MAPPING,
       TF_MODEL_FOR_QUESTION_ANSWERING_MAPPING,
       TF_MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING,
       TF_MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING,
       TF_MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING,
       TFSharedEmbeddings,
   )

   if _tf_gpu_memory_limit is not None:
      __UpperCAmelCase												=   tf.config.list_physical_devices('GPU')
      for gpu in gpus:
         # Restrict TensorFlow to only allocate x GB of memory on the GPUs
         try:
            tf.config.set_logical_device_configuration(
                gpu, [tf.config.LogicalDeviceConfiguration(memory_limit=_tf_gpu_memory_limit)]
            )
            __UpperCAmelCase												=   tf.config.list_logical_devices('GPU')
            print('Logical GPUs', logical_gpus)
         except RuntimeError as e:
            # Virtual devices must be set before GPUs have been initialized
            print(e)


@require_tf
class 		_a     :







   """simple docstring"""




   A		= None
   A		= ()
   A		= ()
   A		= True
   A		= True
   A		= True
   A		= False






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE=False      ):
    SCREAMING_SNAKE_CASE  :  Dict								=		copy.deepcopy(__SCREAMING_SNAKE_CASE      )

    if model_class in get_values(__SCREAMING_SNAKE_CASE      ):
     SCREAMING_SNAKE_CASE  :  List[str]								=		{
         k: tf.tile(tf.expand_dims(__SCREAMING_SNAKE_CASE    ,1      )    ,(1, self.model_tester.num_choices) + (1,) * (v.ndim - 1)      )
         if isinstance(__SCREAMING_SNAKE_CASE    ,tf.Tensor      ) and v.ndim > 0
         else v
         for k, v in inputs_dict.items()
     }

    if return_labels:
     if model_class in get_values(__SCREAMING_SNAKE_CASE      ):
      SCREAMING_SNAKE_CASE  :  Tuple								=		tf.ones(self.model_tester.batch_size    ,dtype=tf.intaa      )
     elif model_class in get_values(__SCREAMING_SNAKE_CASE      ):
      SCREAMING_SNAKE_CASE  :  str								=		tf.zeros(self.model_tester.batch_size    ,dtype=tf.intaa      )
      SCREAMING_SNAKE_CASE  :  List[Any]								=		tf.zeros(self.model_tester.batch_size    ,dtype=tf.intaa      )
     elif model_class in [
         *get_values(__SCREAMING_SNAKE_CASE      ),
         *get_values(__SCREAMING_SNAKE_CASE      ),
     ]:
      SCREAMING_SNAKE_CASE  :  Tuple								=		tf.zeros(self.model_tester.batch_size    ,dtype=tf.intaa      )
     elif model_class in get_values(__SCREAMING_SNAKE_CASE      ):
      SCREAMING_SNAKE_CASE  :  Any								=		tf.zeros(self.model_tester.batch_size    ,dtype=tf.intaa      )
     elif model_class in [
         *get_values(__SCREAMING_SNAKE_CASE      ),
         *get_values(__SCREAMING_SNAKE_CASE      ),
         *get_values(__SCREAMING_SNAKE_CASE      ),
         *get_values(__SCREAMING_SNAKE_CASE      ),
         *get_values(__SCREAMING_SNAKE_CASE      ),
     ]:
      SCREAMING_SNAKE_CASE  :  str								=		tf.zeros(
          (self.model_tester.batch_size, self.model_tester.seq_length)    ,dtype=tf.intaa      )
    return inputs_dict






   @slow
   def 					__a			(       self      ):
    SCREAMING_SNAKE_CASE				, SCREAMING_SNAKE_CASE  :  int								=		self.model_tester.prepare_config_and_inputs_for_common()
    for model_class in self.all_model_classes[:2]:
     SCREAMING_SNAKE_CASE  :  Optional[int]								=		self._prepare_for_class(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
     SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		model_class(__SCREAMING_SNAKE_CASE      )

     @tf.function
     def run_in_graph_mode():
      return model(__SCREAMING_SNAKE_CASE      )

     SCREAMING_SNAKE_CASE  :  int								=		run_in_graph_mode()
     self.assertIsNotNone(__SCREAMING_SNAKE_CASE      )






   @slow
   def 					__a			(       self      ):
    SCREAMING_SNAKE_CASE				, SCREAMING_SNAKE_CASE  :  Optional[Any]								=		self.model_tester.prepare_config_and_inputs_for_common()
    for model_class in self.all_model_classes[:2]:
     SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		self._prepare_for_class(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
     SCREAMING_SNAKE_CASE  :  List[Any]								=		model_class(__SCREAMING_SNAKE_CASE      )

     @tf.function(experimental_compile=__SCREAMING_SNAKE_CASE      )
     def run_in_graph_mode():
      return model(__SCREAMING_SNAKE_CASE      )

     SCREAMING_SNAKE_CASE  :  Any								=		run_in_graph_mode()
     self.assertIsNotNone(__SCREAMING_SNAKE_CASE      )






   @slow
   def 					__a			(       self      ):
    # This is a copy of the test_keras_fit method, but we use XLA compilation instead of eager
    SCREAMING_SNAKE_CASE				, SCREAMING_SNAKE_CASE  :  List[Any]								=		self.model_tester.prepare_config_and_inputs_for_common()
    for model_class in self.all_model_classes[:2]:
     SCREAMING_SNAKE_CASE  :  Dict								=		model_class(__SCREAMING_SNAKE_CASE      )
     if getattr(__SCREAMING_SNAKE_CASE    ,'hf_compute_loss'    ,__SCREAMING_SNAKE_CASE      ):
      # Test that model correctly compute the loss with kwargs
      SCREAMING_SNAKE_CASE  :  Optional[Any]								=		self._prepare_for_class(inputs_dict.copy()    ,__SCREAMING_SNAKE_CASE    ,return_labels=__SCREAMING_SNAKE_CASE      )
      # Is there a better way to remove these decoder inputs?
      SCREAMING_SNAKE_CASE  :  str								=		{
          key: val
          for key, val in prepared_for_class.items()
          if key not in ('head_mask', 'decoder_head_mask', 'cross_attn_head_mask', 'decoder_input_ids')
      }

      SCREAMING_SNAKE_CASE  :  Tuple								=		{
          'labels',
          'label',
          'label_ids',
          'start_positions',
          'start_position',
          'end_positions',
          'end_position',
          'next_sentence_label',
      }
      SCREAMING_SNAKE_CASE  :  Any								=		possible_label_cols.intersection(set(__SCREAMING_SNAKE_CASE      )      )
      self.assertGreater(len(__SCREAMING_SNAKE_CASE      )    ,0    ,msg='No matching label names found!'      )
      SCREAMING_SNAKE_CASE  :  int								=		{key: val for key, val in prepared_for_class.items() if key in label_names}
      SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		{key: val for key, val in prepared_for_class.items() if key not in label_names}
      self.assertGreater(len(__SCREAMING_SNAKE_CASE      )    ,0      )

      # Make sure it works with XLA!
      model.compile(optimizer=tf.keras.optimizers.SGD(0.0      )    ,jit_compile=__SCREAMING_SNAKE_CASE      )
      # Make sure the model fits without crashing regardless of where we pass the labels
      SCREAMING_SNAKE_CASE  :  Optional[Any]								=		model.fit(
          __SCREAMING_SNAKE_CASE    ,validation_data=__SCREAMING_SNAKE_CASE    ,steps_per_epoch=1    ,validation_steps=1    ,shuffle=__SCREAMING_SNAKE_CASE    ,verbose=0    ,)
      SCREAMING_SNAKE_CASE  :  Tuple								=		history.history['loss'][0]
      self.assertTrue(not isnan(__SCREAMING_SNAKE_CASE      )      )
      SCREAMING_SNAKE_CASE  :  Dict								=		history.history['val_loss'][0]
      self.assertTrue(not isnan(__SCREAMING_SNAKE_CASE      )      )

      # Now test it with separate labels, to make sure that path works in XLA too.
      SCREAMING_SNAKE_CASE  :  Optional[Any]								=		model_class(__SCREAMING_SNAKE_CASE      )
      model.compile(optimizer=tf.keras.optimizers.SGD(0.0      )    ,jit_compile=__SCREAMING_SNAKE_CASE      )
      SCREAMING_SNAKE_CASE  :  List[str]								=		model.fit(
          __SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE    ,validation_data=(inputs_minus_labels, labels)    ,steps_per_epoch=1    ,validation_steps=1    ,shuffle=__SCREAMING_SNAKE_CASE    ,verbose=0    ,)

      SCREAMING_SNAKE_CASE  :  List[Any]								=		history.history['loss'][0]
      self.assertTrue(not isnan(__SCREAMING_SNAKE_CASE      )      )
      SCREAMING_SNAKE_CASE  :  Dict								=		history.history['val_loss'][0]
      self.assertTrue(not isnan(__SCREAMING_SNAKE_CASE      )      )






   @slow
   def 					__a			(       self      ):
    SCREAMING_SNAKE_CASE				, SCREAMING_SNAKE_CASE  :  Tuple								=		self.model_tester.prepare_config_and_inputs_for_common()
    SCREAMING_SNAKE_CASE  :  Optional[Any]								=		True
    SCREAMING_SNAKE_CASE  :  str								=		True

    if hasattr(__SCREAMING_SNAKE_CASE    ,'use_cache'      ):
     SCREAMING_SNAKE_CASE  :  Dict								=		True

    SCREAMING_SNAKE_CASE  :  Any								=		getattr(self.model_tester    ,'encoder_seq_length'    ,self.model_tester.seq_length      )
    SCREAMING_SNAKE_CASE  :  int								=		getattr(self.model_tester    ,'key_length'    ,__SCREAMING_SNAKE_CASE      )

    for model_class in self.all_model_classes[:2]:
     SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		self._prepare_for_class(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
     SCREAMING_SNAKE_CASE  :  Optional[Any]								=		model_class(__SCREAMING_SNAKE_CASE      )
     model.build()
     SCREAMING_SNAKE_CASE  :  Dict								=		len(model(__SCREAMING_SNAKE_CASE      )      )

     for key in list(class_inputs_dict.keys()      ):
      # Remove keys not in the serving signature, as the SavedModel will not be compiled to deal with them
      if key not in model.input_signature:
       del class_inputs_dict[key]
      # Check it's a tensor, in case the inputs dict has some bools in it too
      elif isinstance(class_inputs_dict[key]    ,tf.Tensor      ) and class_inputs_dict[key].dtype.is_integer:
       SCREAMING_SNAKE_CASE  :  int								=		tf.cast(class_inputs_dict[key]    ,tf.intaa      )

     if set(class_inputs_dict.keys()      ) != set(model.input_signature.keys()      ):
      continue  # Some models have inputs that the preparation functions don't create, we skip those

     with tempfile.TemporaryDirectory() as tmpdirname:
      model.save_pretrained(__SCREAMING_SNAKE_CASE    ,saved_model=__SCREAMING_SNAKE_CASE      )
      SCREAMING_SNAKE_CASE  :  Tuple								=		os.path.join(__SCREAMING_SNAKE_CASE    ,'saved_model'    ,'1'      )
      SCREAMING_SNAKE_CASE  :  Any								=		tf.keras.models.load_model(__SCREAMING_SNAKE_CASE      )
      SCREAMING_SNAKE_CASE  :  Any								=		model(__SCREAMING_SNAKE_CASE      )

      if self.is_encoder_decoder:
       SCREAMING_SNAKE_CASE  :  Any								=		outputs['encoder_hidden_states']
       SCREAMING_SNAKE_CASE  :  List[Any]								=		outputs['encoder_attentions']
      else:
       SCREAMING_SNAKE_CASE  :  Tuple								=		outputs['hidden_states']
       SCREAMING_SNAKE_CASE  :  int								=		outputs['attentions']

      self.assertEqual(len(__SCREAMING_SNAKE_CASE      )    ,__SCREAMING_SNAKE_CASE      )

      SCREAMING_SNAKE_CASE  :  List[Any]								=		getattr(
          self.model_tester    ,'expected_num_hidden_layers'    ,self.model_tester.num_hidden_layers + 1      )

      self.assertEqual(len(__SCREAMING_SNAKE_CASE      )    ,__SCREAMING_SNAKE_CASE      )
      self.assertListEqual(
          list(output_hidden_states[0].shape[-2:]      )    ,[self.model_tester.seq_length, self.model_tester.hidden_size]    ,)

      self.assertEqual(len(__SCREAMING_SNAKE_CASE      )    ,self.model_tester.num_hidden_layers      )
      self.assertListEqual(
          list(output_attentions[0].shape[-3:]      )    ,[self.model_tester.num_attention_heads, encoder_seq_length, encoder_key_length]    ,)






   @slow
   def 					__a			(       self      ):
    tf.keras.mixed_precision.set_global_policy('mixed_float16'      )

    # try/finally block to ensure subsequent tests run in float32
    try:
     SCREAMING_SNAKE_CASE				, SCREAMING_SNAKE_CASE  :  Optional[int]								=		self.model_tester.prepare_config_and_inputs_for_common()
     for model_class in self.all_model_classes[:2]:
      SCREAMING_SNAKE_CASE  :  Dict								=		self._prepare_for_class(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
      SCREAMING_SNAKE_CASE  :  Optional[int]								=		model_class(__SCREAMING_SNAKE_CASE      )
      SCREAMING_SNAKE_CASE  :  Any								=		model(__SCREAMING_SNAKE_CASE      )

      self.assertIsNotNone(__SCREAMING_SNAKE_CASE      )
    finally:
     tf.keras.mixed_precision.set_global_policy('float32'      )






   @slow
   def 					__a			(       self      ):
    SCREAMING_SNAKE_CASE				, SCREAMING_SNAKE_CASE  :  List[Any]								=		self.model_tester.prepare_config_and_inputs_for_common()
    # head_mask and decoder_head_mask has different shapes than other input args
    if "head_mask" in inputs_dict:
     del inputs_dict["head_mask"]
    if "decoder_head_mask" in inputs_dict:
     del inputs_dict["decoder_head_mask"]
    if "cross_attn_head_mask" in inputs_dict:
     del inputs_dict["cross_attn_head_mask"]
    SCREAMING_SNAKE_CASE  :  str								=		{
        module_member
        for model_class in self.all_model_classes
        for module in (import_module(model_class.__module__      ),)
        for module_member_name in dir(__SCREAMING_SNAKE_CASE      )
        if module_member_name.endswith('MainLayer'      )
        for module_member in (getattr(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      ),)
        if isinstance(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )
        and tf.keras.layers.Layer in module_member.__bases__
        and getattr(__SCREAMING_SNAKE_CASE    ,'_keras_serializable'    ,__SCREAMING_SNAKE_CASE      )
    }

    for main_layer_class in tf_main_layer_classes:
     # T5MainLayer needs an embed_tokens parameter when called without the inputs_embeds parameter
     if "T5" in main_layer_class.__name__:
      # Take the same values than in TFT5ModelTester for this shared layer
      SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		TFSharedEmbeddings(self.model_tester.vocab_size    ,self.model_tester.hidden_size    ,name='shared'      )
      SCREAMING_SNAKE_CASE  :  List[Any]								=		False
      SCREAMING_SNAKE_CASE  :  Optional[int]								=		main_layer_class(__SCREAMING_SNAKE_CASE    ,embed_tokens=__SCREAMING_SNAKE_CASE      )
     else:
      SCREAMING_SNAKE_CASE  :  Optional[Any]								=		main_layer_class(__SCREAMING_SNAKE_CASE      )

     SCREAMING_SNAKE_CASE  :  Optional[Any]								=		{
         name: tf.keras.Input(tensor.shape[1:]    ,dtype=tensor.dtype      ) for name, tensor in inputs_dict.items()
     }

     if hasattr(self.model_tester    ,'num_labels'      ):
      SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		self.model_tester.num_labels
     else:
      SCREAMING_SNAKE_CASE  :  Optional[int]								=		2

     SCREAMING_SNAKE_CASE  :  Dict								=		tf.data.Dataset.from_tensor_slices(
         (inputs_dict, np.ones((self.model_tester.batch_size, self.model_tester.seq_length, num_labels, 1)      ))      ).batch(1      )

     SCREAMING_SNAKE_CASE  :  Dict								=		main_layer(__SCREAMING_SNAKE_CASE      )[0]
     SCREAMING_SNAKE_CASE  :  int								=		tf.keras.layers.Dense(__SCREAMING_SNAKE_CASE    ,activation='softmax'    ,name='outputs'      )(__SCREAMING_SNAKE_CASE      )
     SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		tf.keras.models.Model(inputs=__SCREAMING_SNAKE_CASE    ,outputs=[outputs]      )

     model.compile(loss='binary_crossentropy'    ,optimizer='adam'    ,metrics=['binary_accuracy']      )
     model.fit(__SCREAMING_SNAKE_CASE    ,epochs=1      )

     with tempfile.TemporaryDirectory() as tmpdirname:
      SCREAMING_SNAKE_CASE  :  Optional[int]								=		os.path.join(__SCREAMING_SNAKE_CASE    ,'keras_model.h5'      )
      model.save(__SCREAMING_SNAKE_CASE      )
      if "T5" in main_layer_class.__name__:
       SCREAMING_SNAKE_CASE  :  Tuple								=		tf.keras.models.load_model(
           __SCREAMING_SNAKE_CASE    ,custom_objects={
               main_layer_class.__name__: main_layer_class,
               'TFSharedEmbeddings': TFSharedEmbeddings,
           }    ,)
      else:
       SCREAMING_SNAKE_CASE  :  int								=		tf.keras.models.load_model(
           __SCREAMING_SNAKE_CASE    ,custom_objects={main_layer_class.__name__: main_layer_class}      )
      assert isinstance(__SCREAMING_SNAKE_CASE    ,tf.keras.Model      )
      model(__SCREAMING_SNAKE_CASE      )






   @slow
   def 					__a			(       self      ):
    SCREAMING_SNAKE_CASE				, SCREAMING_SNAKE_CASE  :  str								=		self.model_tester.prepare_config_and_inputs_for_common()

    for model_class in self.all_model_classes[:2]:
     SCREAMING_SNAKE_CASE  :  Any								=		model_class(__SCREAMING_SNAKE_CASE      )

     SCREAMING_SNAKE_CASE  :  Dict								=		copy.deepcopy(__SCREAMING_SNAKE_CASE      )

     if not self.is_encoder_decoder:
      SCREAMING_SNAKE_CASE  :  Any								=		inputs['input_ids']
      del inputs["input_ids"]
     else:
      SCREAMING_SNAKE_CASE  :  Optional[Any]								=		inputs['input_ids']
      SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		inputs.get('decoder_input_ids'    ,__SCREAMING_SNAKE_CASE      )
      del inputs["input_ids"]
      inputs.pop('decoder_input_ids'    ,__SCREAMING_SNAKE_CASE      )

     if not self.is_encoder_decoder:
      SCREAMING_SNAKE_CASE  :  Tuple								=		model.get_input_embeddings()(__SCREAMING_SNAKE_CASE      )
     else:
      SCREAMING_SNAKE_CASE  :  str								=		model.get_input_embeddings()(__SCREAMING_SNAKE_CASE      )
      SCREAMING_SNAKE_CASE  :  Dict								=		model.get_input_embeddings()(__SCREAMING_SNAKE_CASE      )

     SCREAMING_SNAKE_CASE  :  Optional[int]								=		self._prepare_for_class(__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      )

     @tf.function
     def run_in_graph_mode():
      return model(__SCREAMING_SNAKE_CASE      )

     SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		run_in_graph_mode()
     self.assertIsNotNone(__SCREAMING_SNAKE_CASE      )






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      ):
    # special tokens cannot be bad tokens
    SCREAMING_SNAKE_CASE  :  Optional[Any]								=		[]
    if model.config.bos_token_id is not None:
     special_tokens.append(model.config.bos_token_id      )
    if model.config.pad_token_id is not None:
     special_tokens.append(model.config.pad_token_id      )
    if model.config.eos_token_id is not None:
     special_tokens.append(model.config.eos_token_id      )

    # create random bad tokens that are not special tokens
    SCREAMING_SNAKE_CASE  :  str								=		[]
    while len(__SCREAMING_SNAKE_CASE      ) < num_bad_tokens:
     SCREAMING_SNAKE_CASE  :  str								=		tf.squeeze(ids_tensor((1, 1)    ,self.model_tester.vocab_size      )    ,0      ).numpy()[0]
     if token not in special_tokens:
      bad_tokens.append(__SCREAMING_SNAKE_CASE      )
    return bad_tokens






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE      ):
    for token_id in output_ids[0].numpy().tolist():
     self.assertGreaterEqual(__SCREAMING_SNAKE_CASE    ,0      )
     self.assertLess(__SCREAMING_SNAKE_CASE    ,self.model_tester.vocab_size      )






   def 					__a			(       self    ,__SCREAMING_SNAKE_CASE    ,__SCREAMING_SNAKE_CASE      ):
    # for all bad word tokens
    for bad_word_ids in bad_words_ids:
     # for all slices in batch
     for generated_ids_slice in generated_ids:
      # for all word idx
      for i in range(len(__SCREAMING_SNAKE_CASE      )    ,len(__SCREAMING_SNAKE_CASE      )      ):
       # if tokens match
       if generated_ids_slice[i - len(__SCREAMING_SNAKE_CASE      ) : i] == bad_word_ids:
        return True
    return False




'''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)


