'''simple docstring'''




import gc
import unittest

import numpy as np
import torch
from transformers import CLIPTextConfig, CLIPTextModel, CLIPTextModelWithProjection, CLIPTokenizer

from diffusers import (
    AutoencoderKL,
    DiffusionPipeline,
    EulerDiscreteScheduler,
    StableDiffusionXLPipeline,
    UNetaDConditionModel,
)
from diffusers.utils import slow, torch_device
from diffusers.utils.testing_utils import enable_full_determinism, require_torch_gpu

from ..pipeline_params import TEXT_TO_IMAGE_BATCH_PARAMS, TEXT_TO_IMAGE_IMAGE_PARAMS, TEXT_TO_IMAGE_PARAMS
from ..test_pipelines_common import PipelineLatentTesterMixin, PipelineTesterMixin


enable_full_determinism()

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

      __UpperCamelCase:  int      =						StableDiffusionXLPipeline
      __UpperCamelCase:  str      =						TEXT_TO_IMAGE_PARAMS
      __UpperCamelCase:  int      =						TEXT_TO_IMAGE_BATCH_PARAMS
      __UpperCamelCase:  Optional[Any]      =						TEXT_TO_IMAGE_IMAGE_PARAMS
      __UpperCamelCase:  Dict      =						TEXT_TO_IMAGE_IMAGE_PARAMS




      def 					_A     (	self						:    Tuple	):
             torch.manual_seed(0	)
             _UpperCAmelCase					:  Dict											=   UNetaDConditionModel(
                 block_out_channels=(32, 64)						, layers_per_block=2						, sample_size=32						, in_channels=4						, out_channels=4						, down_block_types=("DownBlock2D", "CrossAttnDownBlock2D")						, up_block_types=("CrossAttnUpBlock2D", "UpBlock2D")						, attention_head_dim=(2, 4)						, use_linear_projection=A						, addition_embed_type="text_time"						, addition_time_embed_dim=8						, transformer_layers_per_block=(1, 2)						, projection_class_embeddings_input_dim=80						, cross_attention_dim=64						, )
             _UpperCAmelCase					:  int											=   EulerDiscreteScheduler(
                 beta_start=0.00_085						, beta_end=0.012						, steps_offset=1						, beta_schedule="scaled_linear"						, timestep_spacing="leading"						, )
             torch.manual_seed(0	)
             _UpperCAmelCase					:  Dict											=   AutoencoderKL(
                 block_out_channels=[32, 64]						, in_channels=3						, out_channels=3						, down_block_types=["DownEncoderBlock2D", "DownEncoderBlock2D"]						, up_block_types=["UpDecoderBlock2D", "UpDecoderBlock2D"]						, latent_channels=4						, sample_size=128						, )
             torch.manual_seed(0	)
             _UpperCAmelCase					:  List[str]											=   CLIPTextConfig(
                 bos_token_id=0						, eos_token_id=2						, hidden_size=32						, intermediate_size=37						, layer_norm_eps=1E-05						, num_attention_heads=4						, num_hidden_layers=5						, pad_token_id=1						, vocab_size=1000						, hidden_act="gelu"						, projection_dim=32						, )
             _UpperCAmelCase					:  str											=   CLIPTextModel(A	)
             _UpperCAmelCase					:  Tuple											=   CLIPTokenizer.from_pretrained("hf-internal-testing/tiny-random-clip"						, local_files_only=A	)

             _UpperCAmelCase					:  List[str]											=   CLIPTextModelWithProjection(A	)
             _UpperCAmelCase					:  Union[str, Any]											=   CLIPTokenizer.from_pretrained("hf-internal-testing/tiny-random-clip"						, local_files_only=A	)

             _UpperCAmelCase					:  Any											=   {
                 "unet": unet,
                 "scheduler": scheduler,
                 "vae": vae,
                 "text_encoder": text_encoder,
                 "tokenizer": tokenizer,
                 "text_encoder_2": text_encoder_a,
                 "tokenizer_2": tokenizer_a,
                 # "safety_checker": None,
                 # "feature_extractor": None,
             }
             return components




      def 					_A     (	self						:    Optional[Any]						, A						:    List[Any]						, A						:    str=0	):
             if str(A	).startswith("mps"	):
                    _UpperCAmelCase					:  List[str]											=   torch.manual_seed(A	)
             else:
                    _UpperCAmelCase					:  Tuple											=   torch.Generator(device=A	).manual_seed(A	)
             _UpperCAmelCase					:  int											=   {
                 "prompt": "A painting of a squirrel eating a burger",
                 "generator": generator,
                 "num_inference_steps": 2,
                 "guidance_scale": 5.0,
                 "output_type": "numpy",
             }
             return inputs




      def 					_A     (	self						:    Union[str, Any]	):
             _UpperCAmelCase					:  Tuple											=   "cpu"  # ensure determinism for the device-dependent torch.Generator
             _UpperCAmelCase					:  Union[str, Any]											=   self.get_dummy_components()
             _UpperCAmelCase					:  Optional[int]											=   StableDiffusionXLPipeline(**A	)
             _UpperCAmelCase					:  Optional[Any]											=   sd_pipe.to(A	)
             sd_pipe.set_progress_bar_config(disable=A	)

             _UpperCAmelCase					:  Dict											=   self.get_dummy_inputs(A	)
             _UpperCAmelCase					:  Optional[Any]											=   sd_pipe(**A	).images
             _UpperCAmelCase					:  List[str]											=   image[0, -3:, -3:, -1]

             assert image.shape == (1, 64, 64, 3)
             _UpperCAmelCase					:  Tuple											=   np.array([0.5_873, 0.6_128, 0.4_797, 0.5_122, 0.5_674, 0.4_639, 0.5_227, 0.5_149, 0.4_747]	)

             assert np.abs(image_slice.flatten() - expected_slice	).max() < 1E-2




      def 					_A     (	self						:    Tuple	):
             _UpperCAmelCase					:  Tuple											=   self.get_dummy_components()
             _UpperCAmelCase					:  Optional[int]											=   StableDiffusionXLPipeline(**A	)
             _UpperCAmelCase					:  List[str]											=   sd_pipe.to(A	)
             _UpperCAmelCase					:  Tuple											=   sd_pipe.to(A	)
             sd_pipe.set_progress_bar_config(disable=A	)

             # forward without prompt embeds
             _UpperCAmelCase					:  Optional[int]											=   self.get_dummy_inputs(A	)
             _UpperCAmelCase					:  int											=   3 * ["this is a negative prompt"]
             _UpperCAmelCase					:  List[str]											=   negative_prompt
             _UpperCAmelCase					:  Optional[Any]											=   3 * [inputs["prompt"]]

             _UpperCAmelCase					:  List[str]											=   sd_pipe(**A	)
             _UpperCAmelCase					:  Union[str, Any]											=   output.images[0, -3:, -3:, -1]

             # forward with prompt embeds
             _UpperCAmelCase					:  Optional[int]											=   self.get_dummy_inputs(A	)
             _UpperCAmelCase					:  Optional[int]											=   3 * ["this is a negative prompt"]
             _UpperCAmelCase					:  str											=   3 * [inputs.pop("prompt"	)]

             (
                 (
                 _UpperCAmelCase
             )				,  (
                 _UpperCAmelCase
             )				,  (
                 _UpperCAmelCase
             )				,  (
                 _UpperCAmelCase
             )				,  
             )					:  Union[str, Any]											=   sd_pipe.encode_prompt(A						, negative_prompt=A	)

             _UpperCAmelCase					:  Union[str, Any]											=   sd_pipe(
                 **A						, prompt_embeds=A						, negative_prompt_embeds=A						, pooled_prompt_embeds=A						, negative_pooled_prompt_embeds=A						, )
             _UpperCAmelCase					:  Any											=   output.images[0, -3:, -3:, -1]

             # make sure that it's equal
             assert np.abs(image_slice_a.flatten() - image_slice_a.flatten()	).max() < 1E-4




      def 					_A     (	self						:    Optional[int]	):
             super().test_attention_slicing_forward_pass(expected_max_diff=3E-3	)





      def 					_A     (	self						:    Tuple	):
             super().test_inference_batch_single_identical(expected_max_diff=3E-3	)

@slow
@require_torch_gpu
class      lowerCamelCase_     (unittest.TestCase   ):
      '''simple docstring'''

      def 					_A     (	self						:    Tuple	):
             super().tearDown()
             gc.collect()
             torch.cuda.empty_cache()




      def 					_A     (	self						:    Union[str, Any]						, A						:    Tuple						, A						:    List[Any]="cpu"						, A						:    str=torch.floataa						, A						:    Any=0	):
             _UpperCAmelCase					:  List[Any]											=   torch.Generator(device=A	).manual_seed(A	)
             _UpperCAmelCase					:  Optional[int]											=   np.random.RandomState(A	).standard_normal((1, 4, 64, 64)	)
             _UpperCAmelCase					:  List[Any]											=   torch.from_numpy(A	).to(device=A						, dtype=A	)
             _UpperCAmelCase					:  str											=   {
                 "prompt": "a photograph of an astronaut riding a horse",
                 "latents": latents,
                 "generator": generator,
                 "num_inference_steps": 3,
                 "guidance_scale": 7.5,
                 "output_type": "numpy",
             }
             return inputs





      def 					_A     (	self						:    str	):
             _UpperCAmelCase					:  str											=   DiffusionPipeline.from_pretrained("stabilityai/stable-diffusion-2-base"	)
             pipe.to(A	)
             pipe.set_progress_bar_config(disable=A	)

             _UpperCAmelCase					:  Any											=   self.get_inputs(A	)
             _UpperCAmelCase					:  Optional[int]											=   pipe(**A	).images
             _UpperCAmelCase					:  Tuple											=   image[0, -3:, -3:, -1].flatten()

             assert image.shape == (1, 512, 512, 3)
             _UpperCAmelCase					:  List[str]											=   np.array([0.49_493, 0.47_896, 0.40_798, 0.54_214, 0.53_212, 0.48_202, 0.47_656, 0.46_329, 0.48_506]	)
             assert np.abs(image_slice - expected_slice	).max() < 7E-3


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

