'''simple docstring'''




from __future__ import annotations

import unittest

from transformers import AutoTokenizer, GPTJConfig, is_tf_available
from transformers.testing_utils import require_tf, slow, tooslow

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin
from ...utils.test_modeling_tf_core import TFCoreModelTesterMixin


if is_tf_available():
   import tensorflow as tf

   from transformers.models.gptj.modeling_tf_gptj import (
       TFGPTJForCausalLM,
       TFGPTJForQuestionAnswering,
       TFGPTJForSequenceClassification,
       TFGPTJModel,
       shape_list,
   )

class      lowerCamelCase_     :
      '''simple docstring'''

      def __init__(	self						:    Dict						, A						:    Union[str, Any]	):
             _UpperCAmelCase					:  Any											=   parent
             _UpperCAmelCase					:  str											=   13
             _UpperCAmelCase					:  Tuple											=   7
             _UpperCAmelCase					:  Any											=   True
             _UpperCAmelCase					:  List[str]											=   True
             _UpperCAmelCase					:  str											=   True
             _UpperCAmelCase					:  Tuple											=   True
             _UpperCAmelCase					:  Optional[Any]											=   True
             _UpperCAmelCase					:  Any											=   99
             _UpperCAmelCase					:  Any											=   32
             _UpperCAmelCase					:  List[str]											=   4
             _UpperCAmelCase					:  Dict											=   2
             _UpperCAmelCase					:  List[str]											=   4
             _UpperCAmelCase					:  int											=   37
             _UpperCAmelCase					:  str											=   "gelu"
             _UpperCAmelCase					:  int											=   0.1
             _UpperCAmelCase					:  Tuple											=   0.1
             _UpperCAmelCase					:  Optional[int]											=   512
             _UpperCAmelCase					:  Any											=   16
             _UpperCAmelCase					:  Dict											=   2
             _UpperCAmelCase					:  str											=   0.02
             _UpperCAmelCase					:  Any											=   3
             _UpperCAmelCase					:  List[str]											=   4
             _UpperCAmelCase					:  int											=   None
             _UpperCAmelCase					:  Union[str, Any]											=   self.vocab_size - 1
             _UpperCAmelCase					:  List[str]											=   self.vocab_size - 1
             _UpperCAmelCase					:  Optional[int]											=   self.vocab_size - 1




      def 					_A     (	self						:    Any	):
             _UpperCAmelCase					:  Optional[Any]											=   ids_tensor([self.batch_size, self.seq_length]						, self.vocab_size	)

             _UpperCAmelCase					:  List[str]											=   None
             if self.use_input_mask:
                    _UpperCAmelCase					:  List[Any]											=   random_attention_mask([self.batch_size, self.seq_length]	)

             _UpperCAmelCase					:  List[Any]											=   None
             if self.use_token_type_ids:
                    _UpperCAmelCase					:  Any											=   ids_tensor([self.batch_size, self.seq_length]						, self.type_vocab_size	)

             _UpperCAmelCase					:  Any											=   None
             if self.use_mc_token_ids:
                    _UpperCAmelCase					:  List[str]											=   ids_tensor([self.batch_size, self.num_choices]						, self.seq_length	)

             _UpperCAmelCase					:  str											=   None
             _UpperCAmelCase					:  Optional[Any]											=   None
             _UpperCAmelCase					:  Union[str, Any]											=   None
             if self.use_labels:
                    _UpperCAmelCase					:  str											=   ids_tensor([self.batch_size]						, self.type_sequence_label_size	)
                    _UpperCAmelCase					:  Dict											=   ids_tensor([self.batch_size, self.seq_length]						, self.num_labels	)
                    _UpperCAmelCase					:  List[Any]											=   ids_tensor([self.batch_size]						, self.num_choices	)

             _UpperCAmelCase					:  Any											=   GPTJConfig(
                 vocab_size=self.vocab_size						, n_embd=self.hidden_size						, n_layer=self.num_hidden_layers						, n_head=self.num_attention_heads						, intermediate_size=self.intermediate_size						, hidden_act=self.hidden_act						, hidden_dropout_prob=self.hidden_dropout_prob						, attention_probs_dropout_prob=self.attention_probs_dropout_prob						, n_positions=self.max_position_embeddings						, type_vocab_size=self.type_vocab_size						, initializer_range=self.initializer_range						, bos_token_id=self.bos_token_id						, eos_token_id=self.eos_token_id						, pad_token_id=self.pad_token_id						, rotary_dim=self.rotary_dim						, return_dict=A						, )

             _UpperCAmelCase					:  Any											=   ids_tensor([self.num_hidden_layers, self.num_attention_heads]						, 2	)

             return (
                 config,
                 input_ids,
                 input_mask,
                 head_mask,
                 token_type_ids,
                 mc_token_ids,
                 sequence_labels,
                 token_labels,
                 choice_labels,
             )




      def 					_A     (	self						:    Optional[Any]						, A						:    List[Any]						, A						:    Tuple						, A						:    Optional[int]						, A						:    str						, A						:    List[Any]						, *A						:    Union[str, Any]	):
             _UpperCAmelCase					:  Optional[int]											=   TFGPTJModel(config=A	)
             _UpperCAmelCase					:  Optional[int]											=   {
                 "input_ids": input_ids,
                 "attention_mask": input_mask,
                 "token_type_ids": token_type_ids,
             }
             _UpperCAmelCase					:  Any											=   model(A	)

             _UpperCAmelCase					:  Any											=   [input_ids, None, input_mask]  # None is the input for 'past'
             _UpperCAmelCase					:  str											=   model(A	)

             _UpperCAmelCase					:  int											=   model(A	)

             self.parent.assertEqual(result.last_hidden_state.shape						, (self.batch_size, self.seq_length, self.hidden_size)	)




      def 					_A     (	self						:    Union[str, Any]						, A						:    List[Any]						, A						:    Optional[Any]						, A						:    Dict						, A						:    Optional[Any]						, A						:    Tuple						, *A						:    List[Any]	):
             _UpperCAmelCase					:  Dict											=   TFGPTJModel(config=A	)

             # first forward pass
             _UpperCAmelCase					:  Tuple											=   model(A						, token_type_ids=A						, use_cache=A	)
             _UpperCAmelCase					:  int											=   model(A						, token_type_ids=A	)
             _UpperCAmelCase					:  List[str]											=   model(A						, token_type_ids=A						, use_cache=A	)

             self.parent.assertTrue(len(A	) == len(A	)	)
             self.parent.assertTrue(len(A	) == len(A	) + 1	)

             _UpperCAmelCase					:  int											=   outputs.to_tuple()

             # create hypothetical next token and extent to next_input_ids
             _UpperCAmelCase					:  Dict											=   ids_tensor((self.batch_size, 1)						, config.vocab_size	)
             _UpperCAmelCase					:  Optional[int]											=   ids_tensor([self.batch_size, 1]						, self.type_vocab_size	)

             # append to next input_ids and token_type_ids
             _UpperCAmelCase					:  List[Any]											=   tf.concat([input_ids, next_tokens]						, axis=-1	)
             _UpperCAmelCase					:  Union[str, Any]											=   tf.concat([token_type_ids, next_token_types]						, axis=-1	)

             _UpperCAmelCase					:  int											=   model(A						, token_type_ids=A	)["last_hidden_state"]
             _UpperCAmelCase					:  Dict											=   model(A						, token_type_ids=A						, past_key_values=A	)[
                 "last_hidden_state"
             ]

             # select random slice
             _UpperCAmelCase					:  Union[str, Any]											=   int(ids_tensor((1,)						, shape_list(A	)[-1]	)	)
             _UpperCAmelCase					:  Union[str, Any]											=   output_from_no_past[:, -1, random_slice_idx]
             _UpperCAmelCase					:  Optional[int]											=   output_from_past[:, 0, random_slice_idx]

             # test that outputs are equal for slice
             tf.debugging.assert_near(A						, A						, rtol=1E-6	)




      def 					_A     (	self						:    Union[str, Any]						, A						:    Optional[Any]						, A						:    Union[str, Any]						, A						:    Dict						, A						:    Optional[Any]						, A						:    Dict						, *A						:    str	):
             _UpperCAmelCase					:  Tuple											=   TFGPTJModel(config=A	)

             # create attention mask
             _UpperCAmelCase					:  Optional[Any]											=   self.seq_length // 2
             _UpperCAmelCase					:  Optional[Any]											=   tf.ones((self.batch_size, half_seq_length)						, dtype=tf.intaa	)
             _UpperCAmelCase					:  Any											=   tf.zeros((self.batch_size, self.seq_length - half_seq_length)						, dtype=tf.intaa	)
             _UpperCAmelCase					:  str											=   tf.concat([attn_mask_begin, attn_mask_end]						, axis=1	)

             # first forward pass
             _UpperCAmelCase					:  Optional[int]											=   model(A						, attention_mask=A	).to_tuple()

             # create hypothetical next token and extent to next_input_ids
             _UpperCAmelCase					:  Union[str, Any]											=   ids_tensor((self.batch_size, 1)						, config.vocab_size	)

             # change a random masked slice from input_ids
             _UpperCAmelCase					:  Optional[int]											=   ids_tensor((1,)						, A	).numpy() + 1
             _UpperCAmelCase					:  List[str]											=   ids_tensor((self.batch_size, self.seq_length)						, config.vocab_size	)
             _UpperCAmelCase					:  Tuple											=   tf.range(self.seq_length	) == (self.seq_length - random_seq_idx_to_change)
             _UpperCAmelCase					:  List[Any]											=   tf.transpose(
                 tf.broadcast_to(tf.expand_dims(A						, -1	)						, (self.seq_length, self.batch_size)	)	)
             _UpperCAmelCase					:  Optional[int]											=   tf.where(A						, A						, A	)

             # append to next input_ids and attn_mask
             _UpperCAmelCase					:  Optional[Any]											=   tf.concat([input_ids, next_tokens]						, axis=-1	)
             _UpperCAmelCase					:  Optional[int]											=   tf.concat([attn_mask, tf.ones((shape_list(A	)[0], 1)						, dtype=tf.intaa	)]						, axis=1	)

             # get two different outputs
             _UpperCAmelCase					:  List[Any]											=   model(A						, attention_mask=A	)["last_hidden_state"]
             _UpperCAmelCase					:  Union[str, Any]											=   model(A						, past_key_values=A						, attention_mask=A	)[
                 "last_hidden_state"
             ]

             # select random slice
             _UpperCAmelCase					:  Optional[Any]											=   int(ids_tensor((1,)						, shape_list(A	)[-1]	)	)
             _UpperCAmelCase					:  Dict											=   output_from_no_past[:, -1, random_slice_idx]
             _UpperCAmelCase					:  str											=   output_from_past[:, 0, random_slice_idx]

             # test that outputs are equal for slice
             tf.debugging.assert_near(A						, A						, rtol=1E-12	)




      def 					_A     (	self						:    Any						, A						:    int						, A						:    int						, A						:    Any						, A						:    Any						, A						:    Union[str, Any]						, *A						:    Optional[int]	):
             _UpperCAmelCase					:  Dict											=   TFGPTJModel(config=A	)

             _UpperCAmelCase					:  Optional[int]											=   input_ids[:1, :]
             _UpperCAmelCase					:  Dict											=   input_mask[:1, :]
             _UpperCAmelCase					:  Tuple											=   token_type_ids[:1, :]
             _UpperCAmelCase					:  Optional[Any]											=   1

             # first forward pass
             _UpperCAmelCase					:  Tuple											=   model(A						, attention_mask=A						, token_type_ids=A						, use_cache=A	)

             _UpperCAmelCase					:  Any											=   outputs.to_tuple()

             # create hypothetical next token and extent to next_input_ids
             _UpperCAmelCase					:  List[str]											=   ids_tensor((self.batch_size, 3)						, config.vocab_size	)
             _UpperCAmelCase					:  Tuple											=   ids_tensor((self.batch_size, 3)						, 2	)
             _UpperCAmelCase					:  int											=   ids_tensor((self.batch_size, 3)						, self.type_vocab_size	)

             # append to next input_ids and token_type_ids
             _UpperCAmelCase					:  Dict											=   tf.concat([input_ids, next_tokens]						, axis=-1	)
             _UpperCAmelCase					:  Optional[Any]											=   tf.concat([input_mask, next_attn_mask]						, axis=-1	)
             _UpperCAmelCase					:  List[str]											=   tf.concat([token_type_ids, next_token_types]						, axis=-1	)

             _UpperCAmelCase					:  int											=   model(
                 A						, token_type_ids=A						, attention_mask=A	)["last_hidden_state"]
             _UpperCAmelCase					:  Dict											=   model(
                 A						, token_type_ids=A						, attention_mask=A						, past_key_values=A						, )["last_hidden_state"]
             self.parent.assertTrue(output_from_past.shape[1] == next_tokens.shape[1]	)

             # select random slice
             _UpperCAmelCase					:  Tuple											=   int(ids_tensor((1,)						, shape_list(A	)[-1]	)	)
             _UpperCAmelCase					:  int											=   output_from_no_past[:, -3:, random_slice_idx]
             _UpperCAmelCase					:  Optional[Any]											=   output_from_past[:, :, random_slice_idx]

             # test that outputs are equal for slice
             tf.debugging.assert_near(A						, A						, rtol=1E-3	)




      def 					_A     (	self						:    Optional[int]						, A						:    List[str]						, A						:    List[str]						, A						:    Union[str, Any]						, A						:    List[str]						, A						:    Optional[Any]						, *A						:    Optional[Any]	):
             _UpperCAmelCase					:  Tuple											=   TFGPTJForCausalLM(config=A	)
             _UpperCAmelCase					:  Optional[int]											=   {
                 "input_ids": input_ids,
                 "attention_mask": input_mask,
                 "token_type_ids": token_type_ids,
             }
             _UpperCAmelCase					:  List[str]											=   model(A	)
             self.parent.assertEqual(result.logits.shape						, (self.batch_size, self.seq_length, self.vocab_size)	)





      def 					_A     (	self						:    List[Any]	):
             _UpperCAmelCase					:  List[Any]											=   self.prepare_config_and_inputs()

             (
                 _UpperCAmelCase			
             )					:  int											=   config_and_inputs

             _UpperCAmelCase					:  Union[str, Any]											=   {
                 "input_ids": input_ids,
                 "token_type_ids": token_type_ids,
                 "attention_mask": input_mask,
             }
             return config, inputs_dict

@require_tf
class      lowerCamelCase_     (lowerCamelCase_							,			lowerCamelCase_							,			lowerCamelCase_							,			unittest.TestCase   ):
      '''simple docstring'''

      __UpperCamelCase:  Dict      =						(
          (TFGPTJForCausalLM, TFGPTJForSequenceClassification, TFGPTJForQuestionAnswering, TFGPTJModel)
          if is_tf_available()
          else ()
      )

      __UpperCamelCase:  Union[str, Any]      =						(TFGPTJForCausalLM,) if is_tf_available() else ()
      __UpperCamelCase:  str      =						(
          {
              """feature-extraction""": TFGPTJModel,
              """question-answering""": TFGPTJForQuestionAnswering,
              """text-classification""": TFGPTJForSequenceClassification,
              """text-generation""": TFGPTJForCausalLM,
              """zero-shot""": TFGPTJForSequenceClassification,
          }
          if is_tf_available()
          else {}
      )
      __UpperCamelCase:  List[Any]      =						False
      __UpperCamelCase:  Any      =						False
      __UpperCamelCase:  List[str]      =						False
      __UpperCamelCase:  Dict      =						False




      def 					_A     (	self						:    Optional[int]						, A						:    List[str]						, A						:    Optional[Any]						, A						:    Tuple						, A						:    Optional[Any]						, A						:    Union[str, Any]	):







             if (
                 pipeline_test_casse_name == "QAPipelineTests"
                 and tokenizer_name is not None
                 and not tokenizer_name.endswith("Fast"	)
             ):
                    # `QAPipelineTests` fails for a few models when the slower tokenizer are used.
                    # (The slower tokenizers were never used for pipeline tests before the pipeline testing rework)
                    # TODO: check (and possibly fix) the `QAPipelineTests` with slower tokenizer
                    return True

             return False




      def 					_A     (	self						:    List[str]	):
             _UpperCAmelCase					:  List[Any]											=   TFGPTJModelTester(self	)
             _UpperCAmelCase					:  Dict											=   ConfigTester(self						, config_class=A						, n_embd=37	)




      def 					_A     (	self						:    List[Any]	):
             self.config_tester.run_common_tests()




      def 					_A     (	self						:    int	):
             _UpperCAmelCase					:  List[Any]											=   self.model_tester.prepare_config_and_inputs()
             self.model_tester.create_and_check_gptj_model(*A	)




      def 					_A     (	self						:    List[str]	):
             _UpperCAmelCase					:  List[Any]											=   self.model_tester.prepare_config_and_inputs()
             self.model_tester.create_and_check_gptj_model_past(*A	)




      def 					_A     (	self						:    Optional[Any]	):
             _UpperCAmelCase					:  Optional[Any]											=   self.model_tester.prepare_config_and_inputs()
             self.model_tester.create_and_check_gptj_model_attention_mask_past(*A	)




      def 					_A     (	self						:    Optional[Any]	):
             _UpperCAmelCase					:  Dict											=   self.model_tester.prepare_config_and_inputs()
             self.model_tester.create_and_check_gptj_model_past_large_inputs(*A	)




      def 					_A     (	self						:    Optional[Any]	):
             _UpperCAmelCase					:  Any											=   self.model_tester.prepare_config_and_inputs()
             self.model_tester.create_and_check_gptj_lm_head_model(*A	)




      @slow
      @unittest.skipIf(
          not is_tf_available() or len(tf.config.list_physical_devices("GPU"	)	) > 0						, "skip testing on GPU for now to avoid GPU OOM."						, )
      def 					_A     (	self						:    Any	):
             _UpperCAmelCase					:  Dict											=   TFGPTJModel.from_pretrained("EleutherAI/gpt-j-6B"						, from_pt=A	)
             self.assertIsNotNone(A	)





      @unittest.skip(reason="Currently, model embeddings are going to undergo a major refactor."	)
      def 					_A     (	self						:    List[str]	):
             super().test_resize_token_embeddings()

@require_tf
@tooslow
# Marked as @tooslow due to GPU OOM -- but still useful to run locally. Requires ~39GB of RAM.
class      lowerCamelCase_     (unittest.TestCase   ):
      '''simple docstring'''

      def 					_A     (	self						:    List[str]	):
             _UpperCAmelCase					:  Tuple											=   TFGPTJForCausalLM.from_pretrained("EleutherAI/gpt-j-6B"						, from_pt=A	)
             _UpperCAmelCase					:  Optional[Any]											=   tf.convert_to_tensor([[464, 3290]]						, dtype=tf.intaa	)  # The dog
             # fmt: off
             # The dog is a man's best friend. It is a loyal companion, and it is a friend
             _UpperCAmelCase					:  List[Any]											=   [464, 3290, 318, 257, 582, 338, 1266, 1545, 13, 632, 318, 257, 9112, 15185, 11, 290, 340, 318, 257, 1545]
             # fmt: on
             _UpperCAmelCase					:  int											=   model.generate(A						, do_sample=A	)
             self.assertListEqual(output_ids[0].numpy().tolist()						, A	)




      def 					_A     (	self						:    List[Any]	):
             _UpperCAmelCase					:  Optional[Any]											=   AutoTokenizer.from_pretrained("EleutherAI/gpt-j-6B"						, revision="float16"	)
             _UpperCAmelCase					:  List[str]											=   TFGPTJForCausalLM.from_pretrained("EleutherAI/gpt-j-6B"						, revision="float16"						, from_pt=A	)

             _UpperCAmelCase					:  int											=   tokenizer("Today is a nice day and"						, return_tensors="tf"	)
             # forces the generation to happen on CPU, to avoid GPU-related quirks
             with tf.device(":/CPU:0"	):
                    _UpperCAmelCase					:  Union[str, Any]											=   model.generate(**A						, do_sample=A						, seed=[42, 0]	)
             _UpperCAmelCase					:  Tuple											=   tokenizer.decode(output_ids[0]						, skip_special_tokens=A	)

             _UpperCAmelCase					:  Dict											=   "Today is a nice day and I’m going to go for a walk. I’"
             self.assertEqual(A						, A	)




      def 					_A     (	self						:    Dict	):
             _UpperCAmelCase					:  List[Any]											=   TFGPTJForCausalLM.from_pretrained("EleutherAI/gpt-j-6B"						, revision="float16"						, from_pt=A	)
             _UpperCAmelCase					:  str											=   AutoTokenizer.from_pretrained("EleutherAI/gpt-j-6B"						, revision="float16"	)

             _UpperCAmelCase					:  List[str]											=   "left"

             # Define PAD Token = EOS Token = 50256
             _UpperCAmelCase					:  Any											=   tokenizer.eos_token
             _UpperCAmelCase					:  List[str]											=   model.config.eos_token_id

             # use different length sentences to test batching
             _UpperCAmelCase					:  int											=   [
                 "Hello, my dog is a little",
                 "Today, I",
             ]
             _UpperCAmelCase					:  Any											=   [
                 "Hello, my dog is a little over a year old and has been diagnosed with hip dysplasia",
                 "Today, I’m going to be talking about a topic that’",
             ]
             return model, tokenizer, sentences, expected_output_sentences




      def 					_A     (	self						:    List[str]	):
             _UpperCAmelCase					:  Optional[Any]											=   self._get_beam_search_test_objects()

             _UpperCAmelCase					:  int											=   tokenizer(A						, return_tensors="tf"						, padding=A	)
             _UpperCAmelCase					:  List[str]											=   model.generate(**A						, do_sample=A						, num_beams=2	)
             _UpperCAmelCase					:  Tuple											=   tokenizer.batch_decode(A						, skip_special_tokens=A	)
             self.assertListEqual(A						, A	)




      def 					_A     (	self						:    Optional[int]	):
             _UpperCAmelCase					:  Any											=   self._get_beam_search_test_objects()

             _UpperCAmelCase					:  int											=   tokenizer(A						, return_tensors="tf"						, padding=A	)
             _UpperCAmelCase					:  Any											=   tokenizer(sentences[0]						, return_tensors="tf"	)
             _UpperCAmelCase					:  int											=   model.generate(**A						, do_sample=A						, num_beams=2	)
             _UpperCAmelCase					:  Union[str, Any]											=   (
                 shape_list(inputs_non_padded["input_ids"]	)[-1]
                 - tf.reduce_sum(tf.cast(inputs["attention_mask"][-1]						, tf.intaa	)	).numpy()
             )
             _UpperCAmelCase					:  Union[str, Any]											=   tokenizer(sentences[1]						, return_tensors="tf"	)
             _UpperCAmelCase					:  Tuple											=   model.generate(
                 **A						, do_sample=A						, num_beams=2						, max_length=model.config.max_length - num_paddings	)
             _UpperCAmelCase					:  int											=   tokenizer.decode(output_non_padded[0]						, skip_special_tokens=A	)
             _UpperCAmelCase					:  Union[str, Any]											=   tokenizer.decode(output_padded[0]						, skip_special_tokens=A	)
             self.assertListEqual(A						, [non_padded_sentence, padded_sentence]	)





      def 					_A     (	self						:    Union[str, Any]	):
             _UpperCAmelCase					:  Any											=   self._get_beam_search_test_objects()

             _UpperCAmelCase					:  Tuple											=   tokenizer(A						, return_tensors="tf"						, padding=A	)
             _UpperCAmelCase					:  List[Any]											=   tf.function(model.generate						, jit_compile=A	)
             _UpperCAmelCase					:  Dict											=   xla_generate(**A						, do_sample=A						, num_beams=2	)
             _UpperCAmelCase					:  Optional[Any]											=   tokenizer.batch_decode(A						, skip_special_tokens=A	)
             self.assertListEqual(A						, A	)


'''simple docstring'''




def      UpperCamelCase_							( _UpperCAmelCase  :				int      ,     _UpperCAmelCase  :				list[tuple[int, int, int]]   )   ->   list[tuple[int, int, int]]:


       """simple docstring"""







       _UpperCAmelCase					:  Optional[int]											=   sorted(_UpperCAmelCase      ,     key=lambda _UpperCAmelCase   : edge[2]   )

       _UpperCAmelCase					:  Optional[int]											=   list(range(_UpperCAmelCase   )   )

       def find_parent(_UpperCAmelCase  :				Dict   ):
              if i != parent[i]:
                     _UpperCAmelCase					:  Tuple											=   find_parent(parent[i]   )
              return parent[i]

       _UpperCAmelCase					:  Union[str, Any]											=   0
       _UpperCAmelCase					:  Dict											=   []

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

       return minimum_spanning_tree


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

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

  kruskal(num_nodes, edges)

