





import sys
from collections import defaultdict





class 			lowerCAmelCase__:






       '''simple docstring'''


       def __init__(      self							)			->     Dict:
            _SCREAMING_SNAKE_CASE       :	int						    =							[]




       def     UpperCamelCase_			(      self    ,						__lowerCamelCase							)			->     Any:
            return self.node_position[vertex]




       def     UpperCamelCase_			(      self    ,						__lowerCamelCase    ,						__lowerCamelCase							)			->     str:
            _SCREAMING_SNAKE_CASE       :	str						    =							pos




       def     UpperCamelCase_			(      self    ,						__lowerCamelCase    ,						__lowerCamelCase    ,						__lowerCamelCase    ,						__lowerCamelCase							)			->     List[str]:
            if start > size // 2 - 1:
                 return
            else:
                 if 2 * start + 2 >= size:
                      _SCREAMING_SNAKE_CASE       :	Dict						    =							2 * start + 1
                 else:
                      if heap[2 * start + 1] < heap[2 * start + 2]:
                           _SCREAMING_SNAKE_CASE       :	Union[str, Any]						    =							2 * start + 1
                      else:
                           _SCREAMING_SNAKE_CASE       :	Optional[Any]						    =							2 * start + 2
                 if heap[smallest_child] < heap[start]:
                      _SCREAMING_SNAKE_CASE    ,			_SCREAMING_SNAKE_CASE       :	Union[str, Any]						    =							heap[smallest_child], positions[smallest_child]
                      _SCREAMING_SNAKE_CASE    ,			_SCREAMING_SNAKE_CASE       :	Optional[Any]						    =							(
                          heap[start],
                          positions[start],
                      )
                      _SCREAMING_SNAKE_CASE    ,			_SCREAMING_SNAKE_CASE       :	List[str]						    =							temp, tempa

                      _SCREAMING_SNAKE_CASE       :	int						    =							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     UpperCamelCase_			(      self    ,						__lowerCamelCase    ,						__lowerCamelCase    ,						__lowerCamelCase    ,						__lowerCamelCase							)			->     List[str]:
            _SCREAMING_SNAKE_CASE       :	str						    =							position[index]

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

                 if val < heap[parent]:
                      _SCREAMING_SNAKE_CASE       :	Any						    =							heap[parent]
                      _SCREAMING_SNAKE_CASE       :	Union[str, Any]						    =							position[parent]
                      self.set_position(position[parent]    ,						__lowerCamelCase							)
                 else:
                      _SCREAMING_SNAKE_CASE       :	Dict						    =							val
                      _SCREAMING_SNAKE_CASE       :	Optional[int]						    =							temp
                      self.set_position(__lowerCamelCase    ,						__lowerCamelCase							)
                      break
                 _SCREAMING_SNAKE_CASE       :	List[Any]						    =							parent
            else:
                 _SCREAMING_SNAKE_CASE       :	Optional[int]						    =							val
                 _SCREAMING_SNAKE_CASE       :	Optional[Any]						    =							temp
                 self.set_position(__lowerCamelCase    ,						0							)




       def     UpperCamelCase_			(      self    ,						__lowerCamelCase    ,						__lowerCamelCase							)			->     List[Any]:
            _SCREAMING_SNAKE_CASE       :	Optional[int]						    =							len(__lowerCamelCase							) // 2 - 1
            for i in range(__lowerCamelCase    ,						-1    ,						-1							):
                 self.top_to_bottom(__lowerCamelCase    ,						__lowerCamelCase    ,						len(__lowerCamelCase							)    ,						__lowerCamelCase							)







       def     UpperCamelCase_			(      self    ,						__lowerCamelCase    ,						__lowerCamelCase							)			->     Optional[Any]:
            _SCREAMING_SNAKE_CASE       :	Optional[Any]						    =							positions[0]
            _SCREAMING_SNAKE_CASE       :	Optional[int]						    =							sys.maxsize
            self.top_to_bottom(__lowerCamelCase    ,						0    ,						len(__lowerCamelCase							)    ,						__lowerCamelCase							)
            return temp






def     lowerCamelCase__			(__lowerCamelCase	):
     _SCREAMING_SNAKE_CASE       :	Union[str, Any]						    =							Heap()

     _SCREAMING_SNAKE_CASE       :	Any						    =							[0] * len(__lowerCamelCase	)
     _SCREAMING_SNAKE_CASE       :	Union[str, Any]						    =							[-1] * len(__lowerCamelCase	)  # Neighboring Tree Vertex of selected vertex
     # Minimum Distance of explored vertex with neighboring vertex of partial tree
     # formed in graph
     _SCREAMING_SNAKE_CASE       :	int						    =							[]  # Heap of Distance of vertices from their neighboring vertex
     _SCREAMING_SNAKE_CASE       :	Union[str, Any]						    =							[]

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

     _SCREAMING_SNAKE_CASE       :	str						    =							[]
     _SCREAMING_SNAKE_CASE       :	List[str]						    =							1
     _SCREAMING_SNAKE_CASE       :	Optional[Any]						    =							sys.maxsize
     for neighbor, distance in adjacency_list[0]:
          _SCREAMING_SNAKE_CASE       :	int						    =							0
          _SCREAMING_SNAKE_CASE       :	Tuple						    =							distance
     heap.heapify(__lowerCamelCase,       __lowerCamelCase	)

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


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






from dataclasses import dataclass
from typing import Optional, Tuple, Union

import torch
import torch.nn as nn

from ..configuration_utils import ConfigMixin, register_to_config
from ..utils import BaseOutput, apply_forward_hook
from .modeling_utils import ModelMixin
from .vae import Decoder, DecoderOutput, Encoder, VectorQuantizer





@dataclass
class 			lowerCAmelCase__( __lowercase    ):






       '''simple docstring'''


       __snake_case 			=    42





class 			lowerCAmelCase__( __lowercase  ,     __lowercase    ):






       '''simple docstring'''


       @register_to_config
       def __init__(      self    ,						__lowerCamelCase = 3    ,						__lowerCamelCase = 3    ,						__lowerCamelCase = ("DownEncoderBlock2D",)    ,						__lowerCamelCase = ("UpDecoderBlock2D",)    ,						__lowerCamelCase = (6_4,)    ,						__lowerCamelCase = 1    ,						__lowerCamelCase = "silu"    ,						__lowerCamelCase = 3    ,						__lowerCamelCase = 3_2    ,						__lowerCamelCase = 2_5_6    ,						__lowerCamelCase = 3_2    ,						__lowerCamelCase = None    ,						__lowerCamelCase = 0.1_8215    ,						__lowerCamelCase = "group"    ,						)			->     List[str]:
            super().__init__()

            # pass init params to Encoder
            _SCREAMING_SNAKE_CASE       :	Tuple						    =							Encoder(
                in_channels=__lowerCamelCase    ,						out_channels=__lowerCamelCase    ,						down_block_types=__lowerCamelCase    ,						block_out_channels=__lowerCamelCase    ,						layers_per_block=__lowerCamelCase    ,						act_fn=__lowerCamelCase    ,						norm_num_groups=__lowerCamelCase    ,						double_z=__lowerCamelCase    ,						)

            _SCREAMING_SNAKE_CASE       :	Dict						    =							vq_embed_dim if vq_embed_dim is not None else latent_channels

            _SCREAMING_SNAKE_CASE       :	str						    =							nn.Convad(__lowerCamelCase    ,						__lowerCamelCase    ,						1							)
            _SCREAMING_SNAKE_CASE       :	Tuple						    =							VectorQuantizer(__lowerCamelCase    ,						__lowerCamelCase    ,						beta=0.25    ,						remap=__lowerCamelCase    ,						sane_index_shape=__lowerCamelCase							)
            _SCREAMING_SNAKE_CASE       :	int						    =							nn.Convad(__lowerCamelCase    ,						__lowerCamelCase    ,						1							)

            # pass init params to Decoder
            _SCREAMING_SNAKE_CASE       :	Dict						    =							Decoder(
                in_channels=__lowerCamelCase    ,						out_channels=__lowerCamelCase    ,						up_block_types=__lowerCamelCase    ,						block_out_channels=__lowerCamelCase    ,						layers_per_block=__lowerCamelCase    ,						act_fn=__lowerCamelCase    ,						norm_num_groups=__lowerCamelCase    ,						norm_type=__lowerCamelCase    ,						)




       @apply_forward_hook
       def     UpperCamelCase_			(      self    ,						__lowerCamelCase    ,						__lowerCamelCase = True							)			->     VQEncoderOutput:
            _SCREAMING_SNAKE_CASE       :	Optional[int]						    =							self.encoder(__lowerCamelCase							)
            _SCREAMING_SNAKE_CASE       :	Any						    =							self.quant_conv(__lowerCamelCase							)

            if not return_dict:
                 return (h,)

            return VQEncoderOutput(latents=__lowerCamelCase							)




       @apply_forward_hook
       def     UpperCamelCase_			(      self    ,						__lowerCamelCase    ,						__lowerCamelCase = False    ,						__lowerCamelCase = True							)			->     Union[DecoderOutput, torch.FloatTensor]:
            # also go through quantization layer
            if not force_not_quantize:
                 _SCREAMING_SNAKE_CASE    ,			_SCREAMING_SNAKE_CASE    ,			_SCREAMING_SNAKE_CASE       :	Optional[int]						    =							self.quantize(__lowerCamelCase							)
            else:
                 _SCREAMING_SNAKE_CASE       :	Dict						    =							h
            _SCREAMING_SNAKE_CASE       :	str						    =							self.post_quant_conv(__lowerCamelCase							)
            _SCREAMING_SNAKE_CASE       :	Dict						    =							self.decoder(__lowerCamelCase    ,						quant if self.config.norm_type == "spatial" else None							)

            if not return_dict:
                 return (dec,)

            return DecoderOutput(sample=__lowerCamelCase							)







       def     UpperCamelCase_			(      self    ,						__lowerCamelCase    ,						__lowerCamelCase = True							)			->     Union[DecoderOutput, torch.FloatTensor]:
            _SCREAMING_SNAKE_CASE       :	List[Any]						    =							sample
            _SCREAMING_SNAKE_CASE       :	List[str]						    =							self.encode(__lowerCamelCase							).latents
            _SCREAMING_SNAKE_CASE       :	List[str]						    =							self.decode(__lowerCamelCase							).sample

            if not return_dict:
                 return (dec,)

            return DecoderOutput(sample=__lowerCamelCase							)