


'''simple docstring'''



import sys
from collections import defaultdict





class   UpperCAmelCase_    :





    """simple docstring"""






    def __init__(				self      )							->	int:
         __lowerCamelCase  :      Any														=						[]







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_      )							->	Any:
         return self.node_position[vertex]







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	Tuple:
         __lowerCamelCase  :      Optional[int]														=						pos







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	int:
         if start > size // 2 - 1:
              return
         else:
              if 2 * start + 2 >= size:
                   __lowerCamelCase  :      str														=						2 * start + 1
              else:
                   if heap[2 * start + 1] < heap[2 * start + 2]:
                        __lowerCamelCase  :      Optional[Any]														=						2 * start + 1
                   else:
                        __lowerCamelCase  :      int														=						2 * start + 2
              if heap[smallest_child] < heap[start]:
                   __lowerCamelCase							,			__lowerCamelCase  :      Optional[Any]														=						heap[smallest_child], positions[smallest_child]
                   __lowerCamelCase							,			__lowerCamelCase  :      int														=						(
                       heap[start],
                       positions[start],
                   )
                   __lowerCamelCase							,			__lowerCamelCase  :      str														=						temp, tempa

                   __lowerCamelCase  :      Dict														=						self.get_position(positions[smallest_child]      )
                   self.set_position(
                       positions[smallest_child]     ,	self.get_position(positions[start]      )      )
                   self.set_position(positions[start]     ,	SCREAMING_SNAKE_CASE_      )

                   self.top_to_bottom(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	Any:
         __lowerCamelCase  :      Any														=						position[index]

         while index != 0:
              __lowerCamelCase  :      Union[str, Any]														=						int((index - 2) / 2      ) if index % 2 == 0 else int((index - 1) / 2      )

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







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







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	List[Any]:
         __lowerCamelCase  :      Any														=						positions[0]
         __lowerCamelCase  :      Union[str, Any]														=						sys.maxsize
         self.top_to_bottom(SCREAMING_SNAKE_CASE_     ,	0     ,	len(SCREAMING_SNAKE_CASE_      )     ,	SCREAMING_SNAKE_CASE_      )
         return temp







def      UpperCAmelCase__   (      UpperCAmelCase_       :							Optional[int]				)	->						str:
     __lowerCamelCase  :      List[Any]														=						Heap()

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

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

     __lowerCamelCase  :      Tuple														=						[]
     __lowerCamelCase  :      Dict														=						1
     __lowerCamelCase  :      str														=						sys.maxsize
     for neighbor, distance in adjacency_list[0]:
          __lowerCamelCase  :      Any														=						0
          __lowerCamelCase  :      Any														=						distance
     heap.heapify(UpperCAmelCase_ ,       UpperCAmelCase_				)

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


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










'''simple docstring'''



from dataclasses import asdict, dataclass
from typing import Optional

from ...configuration_utils import PretrainedConfig
from ...utils import logging


A__						:   List[str]				=    logging.get_logger(__name__)

# TODO Update this
A__						:   Tuple				=    {
    """facebook/esm-1b""": """https://huggingface.co/facebook/esm-1b/resolve/main/config.json""",
    # See all ESM models at https://huggingface.co/models?filter=esm
}





class   UpperCAmelCase_    (_UpperCAmelCase    ):





    """simple docstring"""






    lowerCamelCase    :   Tuple					=     'esm'







    def __init__(				self     ,	SCREAMING_SNAKE_CASE_=None     ,	SCREAMING_SNAKE_CASE_=None     ,	SCREAMING_SNAKE_CASE_=None     ,	SCREAMING_SNAKE_CASE_=7_68     ,	SCREAMING_SNAKE_CASE_=12     ,	SCREAMING_SNAKE_CASE_=12     ,	SCREAMING_SNAKE_CASE_=30_72     ,	SCREAMING_SNAKE_CASE_=0.1     ,	SCREAMING_SNAKE_CASE_=0.1     ,	SCREAMING_SNAKE_CASE_=10_26     ,	SCREAMING_SNAKE_CASE_=0.0_2     ,	SCREAMING_SNAKE_CASE_=1E-12     ,	SCREAMING_SNAKE_CASE_="absolute"     ,	SCREAMING_SNAKE_CASE_=True     ,	SCREAMING_SNAKE_CASE_=None     ,	SCREAMING_SNAKE_CASE_=False     ,	SCREAMING_SNAKE_CASE_=False     ,	SCREAMING_SNAKE_CASE_=None     ,	SCREAMING_SNAKE_CASE_=None     ,	**SCREAMING_SNAKE_CASE_     ,	)							->	List[str]:
         super().__init__(pad_token_id=SCREAMING_SNAKE_CASE_     ,	mask_token_id=SCREAMING_SNAKE_CASE_     ,	**SCREAMING_SNAKE_CASE_      )

         __lowerCamelCase  :      int														=						vocab_size
         __lowerCamelCase  :      List[Any]														=						hidden_size
         __lowerCamelCase  :      str														=						num_hidden_layers
         __lowerCamelCase  :      List[str]														=						num_attention_heads
         __lowerCamelCase  :      Any														=						intermediate_size
         __lowerCamelCase  :      Optional[Any]														=						hidden_dropout_prob
         __lowerCamelCase  :      Tuple														=						attention_probs_dropout_prob
         __lowerCamelCase  :      Optional[int]														=						max_position_embeddings
         __lowerCamelCase  :      str														=						initializer_range
         __lowerCamelCase  :      Optional[int]														=						layer_norm_eps
         __lowerCamelCase  :      List[str]														=						position_embedding_type
         __lowerCamelCase  :      int														=						use_cache
         __lowerCamelCase  :      Optional[Any]														=						emb_layer_norm_before
         __lowerCamelCase  :      Optional[Any]														=						token_dropout
         __lowerCamelCase  :      str														=						is_folding_model
         if is_folding_model:
              if esmfold_config is None:
                   logger.info('No esmfold_config supplied for folding model, using default values.'      )
                   __lowerCamelCase  :      Dict														=						EsmFoldConfig()
              elif isinstance(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      ):
                   __lowerCamelCase  :      Optional[int]														=						EsmFoldConfig(**SCREAMING_SNAKE_CASE_      )
              __lowerCamelCase  :      List[Any]														=						esmfold_config
              if vocab_list is None:
                   logger.warning('No vocab_list supplied for folding model, assuming the ESM-2 vocabulary!'      )
                   __lowerCamelCase  :      List[str]														=						get_default_vocab_list()
              else:
                   __lowerCamelCase  :      Optional[Any]														=						vocab_list
         else:
              __lowerCamelCase  :      Dict														=						None
              __lowerCamelCase  :      Optional[Any]														=						None
         if self.esmfold_config is not None and getattr(self.esmfold_config     ,	'use_esm_attn_map'     ,	SCREAMING_SNAKE_CASE_      ):
              raise ValueError('The HuggingFace port of ESMFold does not support use_esm_attn_map at this time!'      )







    def  lowercase_							(				self      )							->	Any:
         __lowerCamelCase  :      Any														=						super().to_dict()
         if isinstance(self.esmfold_config     ,	SCREAMING_SNAKE_CASE_      ):
              __lowerCamelCase  :      int														=						self.esmfold_config.to_dict()
         return output







@dataclass
class   UpperCAmelCase_    :





    """simple docstring"""






    lowerCamelCase    :   str					=     None
    lowerCamelCase    :   bool					=     True
    lowerCamelCase    :   bool					=     False
    lowerCamelCase    :   bool					=     False
    lowerCamelCase    :   bool					=     False
    lowerCamelCase    :   float					=     0

    lowerCamelCase    :   bool					=     True
    lowerCamelCase    :   bool					=     False

    lowerCamelCase    :   int					=     1_2_8
    lowerCamelCase    :   "TrunkConfig"					=     None







    def  lowercase_							(				self      )							->	Any:
         if self.trunk is None:
              __lowerCamelCase  :      List[str]														=						TrunkConfig()
         elif isinstance(self.trunk     ,	SCREAMING_SNAKE_CASE_      ):
              __lowerCamelCase  :      Any														=						TrunkConfig(**self.trunk      )







    def  lowercase_							(				self      )							->	int:
         __lowerCamelCase  :      Optional[int]														=						asdict(self      )
         __lowerCamelCase  :      str														=						self.trunk.to_dict()
         return output







@dataclass
class   UpperCAmelCase_    :





    """simple docstring"""






    lowerCamelCase    :   int					=     4_8
    lowerCamelCase    :   int					=     1_0_2_4
    lowerCamelCase    :   int					=     1_2_8
    lowerCamelCase    :   int					=     3_2
    lowerCamelCase    :   int					=     3_2
    lowerCamelCase    :   int					=     3_2
    lowerCamelCase    :   float					=     0
    lowerCamelCase    :   float					=     0
    lowerCamelCase    :   bool					=     False
    lowerCamelCase    :   int					=     4
    lowerCamelCase    :   Optional[int]					=     1_2_8
    lowerCamelCase    :   "StructureModuleConfig"					=     None







    def  lowercase_							(				self      )							->	Optional[int]:
         if self.structure_module is None:
              __lowerCamelCase  :      Dict														=						StructureModuleConfig()
         elif isinstance(self.structure_module     ,	SCREAMING_SNAKE_CASE_      ):
              __lowerCamelCase  :      Optional[Any]														=						StructureModuleConfig(**self.structure_module      )

         if self.max_recycles <= 0:
              raise ValueError(f'`max_recycles` should be positive, got {self.max_recycles}.'      )
         if self.sequence_state_dim % self.sequence_state_dim != 0:
              raise ValueError(
                  '`sequence_state_dim` should be a round multiple of `sequence_state_dim`, got'
                  f' {self.sequence_state_dim} and {self.sequence_state_dim}.'      )
         if self.pairwise_state_dim % self.pairwise_state_dim != 0:
              raise ValueError(
                  '`pairwise_state_dim` should be a round multiple of `pairwise_state_dim`, got'
                  f' {self.pairwise_state_dim} and {self.pairwise_state_dim}.'      )

         __lowerCamelCase  :      Tuple														=						self.sequence_state_dim // self.sequence_head_width
         __lowerCamelCase  :      str														=						self.pairwise_state_dim // self.pairwise_head_width

         if self.sequence_state_dim != sequence_num_heads * self.sequence_head_width:
              raise ValueError(
                  '`sequence_state_dim` should be equal to `sequence_num_heads * sequence_head_width, got'
                  f' {self.sequence_state_dim} != {sequence_num_heads} * {self.sequence_head_width}.'      )
         if self.pairwise_state_dim != pairwise_num_heads * self.pairwise_head_width:
              raise ValueError(
                  '`pairwise_state_dim` should be equal to `pairwise_num_heads * pairwise_head_width, got'
                  f' {self.pairwise_state_dim} != {pairwise_num_heads} * {self.pairwise_head_width}.'      )
         if self.pairwise_state_dim % 2 != 0:
              raise ValueError(f'`pairwise_state_dim` should be even, got {self.pairwise_state_dim}.'      )

         if self.dropout >= 0.4:
              raise ValueError(f'`dropout` should not be greater than 0.4, got {self.dropout}.'      )







    def  lowercase_							(				self      )							->	List[Any]:
         __lowerCamelCase  :      List[str]														=						asdict(self      )
         __lowerCamelCase  :      int														=						self.structure_module.to_dict()
         return output







@dataclass
class   UpperCAmelCase_    :





    """simple docstring"""






    lowerCamelCase    :   int					=     3_8_4
    lowerCamelCase    :   int					=     1_2_8
    lowerCamelCase    :   int					=     1_6
    lowerCamelCase    :   int					=     1_2_8
    lowerCamelCase    :   int					=     1_2
    lowerCamelCase    :   int					=     4
    lowerCamelCase    :   int					=     8
    lowerCamelCase    :   float					=     0.1
    lowerCamelCase    :   int					=     8
    lowerCamelCase    :   int					=     1
    lowerCamelCase    :   int					=     2
    lowerCamelCase    :   int					=     7
    lowerCamelCase    :   int					=     1_0
    lowerCamelCase    :   float					=     1e-8
    lowerCamelCase    :   float					=     1e5







    def  lowercase_							(				self      )							->	Any:
         return asdict(self      )







def      UpperCAmelCase__   (      )	->						Optional[Any]:
     return (
         "<cls>",
         "<pad>",
         "<eos>",
         "<unk>",
         "L",
         "A",
         "G",
         "V",
         "S",
         "E",
         "R",
         "T",
         "I",
         "D",
         "P",
         "K",
         "Q",
         "N",
         "F",
         "Y",
         "M",
         "H",
         "W",
         "C",
         "X",
         "B",
         "U",
         "Z",
         "O",
         ".",
         "-",
         "<null_1>",
         "<mask>",
     )






