



import sys
from collections import defaultdict



class    UpperCAmelCase__:

   '''simple docstring'''




   def __init__(    self	:      List[Any])						->					Optional[int]:




         """simple docstring"""

         lowercase__  =	[]


   def       UpperCAmelCase		(    self	:      Optional[Any]      ,					lowerCAmelCase	:      Tuple)						->					str:




         """simple docstring"""

         return self.node_position[vertex]


   def       UpperCAmelCase		(    self	:      Tuple      ,					lowerCAmelCase	:      str      ,					lowerCAmelCase	:      Optional[Any])						->					Optional[int]:




         """simple docstring"""

         lowercase__  =	pos


   def       UpperCAmelCase		(    self	:      Any      ,					lowerCAmelCase	:      List[Any]      ,					lowerCAmelCase	:      Tuple      ,					lowerCAmelCase	:      Optional[int]      ,					lowerCAmelCase	:      Union[str, Any])						->					Any:




         """simple docstring"""

         if start > size // 2 - 1:
               return
         else:
               if 2 * start + 2 >= size:
                     lowercase__  =	2 * start + 1
               else:
                     if heap[2 * start + 1] < heap[2 * start + 2]:
                           lowercase__  =	2 * start + 1
                     else:
                           lowercase__  =	2 * start + 2
               if heap[smallest_child] < heap[start]:
                     lowercase__,						lowercase__  =	heap[smallest_child], positions[smallest_child]
                     lowercase__,						lowercase__  =	(
                         heap[start],
                         positions[start],
                     )
                     lowercase__,						lowercase__  =	temp, tempa

                     lowercase__  =	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	:      Union[str, Any]      ,					lowerCAmelCase	:      Dict      ,					lowerCAmelCase	:      List[Any]      ,					lowerCAmelCase	:      Union[str, Any]      ,					lowerCAmelCase	:      Union[str, Any])						->					Optional[Any]:




         """simple docstring"""

         lowercase__  =	position[index]

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

               if val < heap[parent]:
                     lowercase__  =	heap[parent]
                     lowercase__  =	position[parent]
                     self.set_position(position[parent]      ,					lowerCAmelCase)
               else:
                     lowercase__  =	val
                     lowercase__  =	temp
                     self.set_position(lowerCAmelCase      ,					lowerCAmelCase)
                     break
               lowercase__  =	parent
         else:
               lowercase__  =	val
               lowercase__  =	temp
               self.set_position(lowerCAmelCase      ,					0)


   def       UpperCAmelCase		(    self	:      List[Any]      ,					lowerCAmelCase	:      Union[str, Any]      ,					lowerCAmelCase	:      Dict)						->					str:




         """simple docstring"""

         lowercase__  =	len(lowerCAmelCase) // 2 - 1
         for i in range(lowerCAmelCase      ,					-1      ,					-1):
               self.top_to_bottom(lowerCAmelCase      ,					lowerCAmelCase      ,					len(lowerCAmelCase)      ,					lowerCAmelCase)



   def       UpperCAmelCase		(    self	:      Optional[int]      ,					lowerCAmelCase	:      str      ,					lowerCAmelCase	:      Any)						->					int:




         """simple docstring"""

         lowercase__  =	positions[0]
         lowercase__  =	sys.maxsize
         self.top_to_bottom(lowerCAmelCase      ,					0      ,					len(lowerCAmelCase)      ,					lowerCAmelCase)
         return temp

def 	_lowerCAmelCase (    A__						):
      lowercase__  =	Heap()

      lowercase__  =	[0] * len(A__						)
      lowercase__  =	[-1] * len(A__						)  # Neighboring Tree Vertex of selected vertex
      # Minimum Distance of explored vertex with neighboring vertex of partial tree
      # formed in graph
      lowercase__  =	[]  # Heap of Distance of vertices from their neighboring vertex
      lowercase__  =	[]

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

      lowercase__  =	[]
      lowercase__  =	1
      lowercase__  =	sys.maxsize
      for neighbor, distance in adjacency_list[0]:
            lowercase__  =	0
            lowercase__  =	distance
      heap.heapify(A__    ,	A__						)

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


if __name__ == "__main__":  # pragma: no cover
       # < --------- Prims Algorithm --------- >
       a__   :					List[str] 						=      int(input("Enter number of edges: ").strip())
       a__   :					Optional[Any] 						=      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))





from collections import OrderedDict
from typing import Any, Mapping, Optional

from ... import PreTrainedTokenizer
from ...configuration_utils import PretrainedConfig
from ...onnx import OnnxConfig, OnnxConfigWithPast, OnnxSeqaSeqConfigWithPast
from ...onnx.utils import compute_effective_axis_dimension
from ...utils import TensorType, is_torch_available, logging


a__   :					int 						=      logging.get_logger(__name__)

a__   :					int 						=      {
    "Helsinki-NLP/opus-mt-en-de": "https://huggingface.co/Helsinki-NLP/opus-mt-en-de/resolve/main/config.json",
    # See all Marian models at https://huggingface.co/models?filter=marian
}



class    UpperCAmelCase__(				lowerCamelCase						):

   '''simple docstring'''




   A     :	Union[str, Any]												=     "marian"
   A     :	Dict												=     ["past_key_values"]
   A     :	List[Any]												=     {"num_attention_heads": "encoder_attention_heads", "hidden_size": "d_model"}


   def __init__(    self	:      Any      ,					lowerCAmelCase	:      List[Any]=5_81_01      ,					lowerCAmelCase	:      Optional[int]=None      ,					lowerCAmelCase	:      List[str]=10_24      ,					lowerCAmelCase	:      int=12      ,					lowerCAmelCase	:      Union[str, Any]=40_96      ,					lowerCAmelCase	:      int=16      ,					lowerCAmelCase	:      Dict=12      ,					lowerCAmelCase	:      Optional[int]=40_96      ,					lowerCAmelCase	:      str=16      ,					lowerCAmelCase	:      List[Any]=0.0      ,					lowerCAmelCase	:      Optional[Any]=0.0      ,					lowerCAmelCase	:      List[str]=True      ,					lowerCAmelCase	:      Union[str, Any]=True      ,					lowerCAmelCase	:      List[Any]="gelu"      ,					lowerCAmelCase	:      int=10_24      ,					lowerCAmelCase	:      Optional[int]=0.1      ,					lowerCAmelCase	:      Optional[int]=0.0      ,					lowerCAmelCase	:      Tuple=0.0      ,					lowerCAmelCase	:      List[Any]=0.02      ,					lowerCAmelCase	:      Union[str, Any]=5_81_00      ,					lowerCAmelCase	:      str=False      ,					lowerCAmelCase	:      Optional[Any]=5_81_00      ,					lowerCAmelCase	:      Union[str, Any]=0      ,					lowerCAmelCase	:      Optional[Any]=0      ,					lowerCAmelCase	:      int=True      ,					**lowerCAmelCase	:      List[str]      ,					)						->					Dict:




         """simple docstring"""

         lowercase__  =	vocab_size
         lowercase__  =	decoder_vocab_size or vocab_size
         lowercase__  =	max_position_embeddings
         lowercase__  =	d_model
         lowercase__  =	encoder_ffn_dim
         lowercase__  =	encoder_layers
         lowercase__  =	encoder_attention_heads
         lowercase__  =	decoder_ffn_dim
         lowercase__  =	decoder_layers
         lowercase__  =	decoder_attention_heads
         lowercase__  =	dropout
         lowercase__  =	attention_dropout
         lowercase__  =	activation_dropout
         lowercase__  =	activation_function
         lowercase__  =	init_std
         lowercase__  =	encoder_layerdrop
         lowercase__  =	decoder_layerdrop
         lowercase__  =	use_cache
         lowercase__  =	encoder_layers
         lowercase__  =	scale_embedding  # scale factor will be sqrt(d_model) if True
         lowercase__  =	share_encoder_decoder_embeddings
         super().__init__(
             pad_token_id=lowerCAmelCase      ,					eos_token_id=lowerCAmelCase      ,					is_encoder_decoder=lowerCAmelCase      ,					decoder_start_token_id=lowerCAmelCase      ,					forced_eos_token_id=lowerCAmelCase      ,					**lowerCAmelCase      ,					)



class    UpperCAmelCase__(				lowerCamelCase						):

   '''simple docstring'''




   @property
   # Copied from transformers.models.bart.configuration_bart.BartOnnxConfig.inputs
   def       UpperCAmelCase		(    self	:      List[Any])						->					Mapping[str, Mapping[int, str]]:




         """simple docstring"""

         if self.task in ["default", "seq2seq-lm"]:
               lowercase__  =	OrderedDict(
                   [
                       ('input_ids', {0: 'batch', 1: 'encoder_sequence'}),
                       ('attention_mask', {0: 'batch', 1: 'encoder_sequence'}),
                   ])

               if self.use_past:
                     lowercase__  =	{0: 'batch'}
                     lowercase__  =	{0: 'batch', 1: 'past_decoder_sequence + sequence'}
               else:
                     lowercase__  =	{0: 'batch', 1: 'decoder_sequence'}
                     lowercase__  =	{0: 'batch', 1: 'decoder_sequence'}

               if self.use_past:
                     self.fill_with_past_key_values_(lowerCAmelCase      ,					direction='inputs')
         elif self.task == "causal-lm":
               # TODO: figure this case out.
               lowercase__  =	OrderedDict(
                   [
                       ('input_ids', {0: 'batch', 1: 'encoder_sequence'}),
                       ('attention_mask', {0: 'batch', 1: 'encoder_sequence'}),
                   ])
               if self.use_past:
                     lowercase__,						lowercase__  =	self.num_layers
                     for i in range(lowerCAmelCase):
                           lowercase__  =	{0: 'batch', 2: 'past_sequence + sequence'}
                           lowercase__  =	{0: 'batch', 2: 'past_sequence + sequence'}
         else:
               lowercase__  =	OrderedDict(
                   [
                       ('input_ids', {0: 'batch', 1: 'encoder_sequence'}),
                       ('attention_mask', {0: 'batch', 1: 'encoder_sequence'}),
                       ('decoder_input_ids', {0: 'batch', 1: 'decoder_sequence'}),
                       ('decoder_attention_mask', {0: 'batch', 1: 'decoder_sequence'}),
                   ])

         return common_inputs


   @property
   # Copied from transformers.models.bart.configuration_bart.BartOnnxConfig.outputs
   def       UpperCAmelCase		(    self	:      Any)						->					Mapping[str, Mapping[int, str]]:




         """simple docstring"""

         if self.task in ["default", "seq2seq-lm"]:
               lowercase__  =	super().outputs
         else:
               lowercase__  =	super(lowerCAmelCase      ,					self).outputs
               if self.use_past:
                     lowercase__,						lowercase__  =	self.num_layers
                     for i in range(lowerCAmelCase):
                           lowercase__  =	{0: 'batch', 2: 'past_sequence + sequence'}
                           lowercase__  =	{0: 'batch', 2: 'past_sequence + sequence'}
         return common_outputs


   def       UpperCAmelCase		(    self	:      Optional[int]      ,					lowerCAmelCase	:      PreTrainedTokenizer      ,					lowerCAmelCase	:      int = -1      ,					lowerCAmelCase	:      int = -1      ,					lowerCAmelCase	:      bool = False      ,					lowerCAmelCase	:      Optional[TensorType] = None      ,					)						->					Mapping[str, Any]:




         """simple docstring"""

         lowercase__  =	self._generate_dummy_inputs_for_encoder_and_decoder(
             lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase)

         # Generate decoder inputs
         lowercase__  =	seq_length if not self.use_past else 1
         lowercase__  =	self._generate_dummy_inputs_for_encoder_and_decoder(
             lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase)
         lowercase__  =	{f'''decoder_{name}''': tensor for name, tensor in decoder_inputs.items()}
         lowercase__  =	dict(**lowerCAmelCase      ,					**lowerCAmelCase)

         if self.use_past:
               if not is_torch_available():
                     raise ValueError('Cannot generate dummy past_keys inputs without PyTorch installed.')
               else:
                     import torch
               lowercase__,						lowercase__  =	common_inputs['input_ids'].shape
               lowercase__  =	common_inputs['decoder_input_ids'].shape[1]
               lowercase__,						lowercase__  =	self.num_attention_heads
               lowercase__  =	(
                   batch,
                   num_encoder_attention_heads,
                   encoder_seq_length,
                   self._config.hidden_size // num_encoder_attention_heads,
               )
               lowercase__  =	decoder_seq_length + 3
               lowercase__  =	(
                   batch,
                   num_decoder_attention_heads,
                   decoder_past_length,
                   self._config.hidden_size // num_decoder_attention_heads,
               )

               lowercase__  =	torch.cat(
                   [common_inputs['decoder_attention_mask'], torch.ones(lowerCAmelCase      ,					lowerCAmelCase)]      ,					dim=1)

               lowercase__  =	[]
               # If the number of encoder and decoder layers are present in the model configuration, both are considered
               lowercase__,						lowercase__  =	self.num_layers
               lowercase__  =	min(lowerCAmelCase      ,					lowerCAmelCase)
               lowercase__  =	max(lowerCAmelCase      ,					lowerCAmelCase) - min_num_layers
               lowercase__  =	'encoder' if num_encoder_layers > num_decoder_layers else 'decoder'

               for _ in range(lowerCAmelCase):
                     common_inputs["past_key_values"].append(
                         (
                             torch.zeros(lowerCAmelCase),
                             torch.zeros(lowerCAmelCase),
                             torch.zeros(lowerCAmelCase),
                             torch.zeros(lowerCAmelCase),
                         ))
               # TODO: test this.
               lowercase__  =	encoder_shape if remaining_side_name == 'encoder' else decoder_shape
               for _ in range(lowerCAmelCase      ,					lowerCAmelCase):
                     common_inputs["past_key_values"].append((torch.zeros(lowerCAmelCase), torch.zeros(lowerCAmelCase)))
         return common_inputs


   def       UpperCAmelCase		(    self	:      str      ,					lowerCAmelCase	:      PreTrainedTokenizer      ,					lowerCAmelCase	:      int = -1      ,					lowerCAmelCase	:      int = -1      ,					lowerCAmelCase	:      bool = False      ,					lowerCAmelCase	:      Optional[TensorType] = None      ,					)						->					Mapping[str, Any]:




         """simple docstring"""

         lowercase__  =	self._generate_dummy_inputs_for_encoder_and_decoder(
             lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase)

         if self.use_past:
               if not is_torch_available():
                     raise ValueError('Cannot generate dummy past_keys inputs without PyTorch installed.')
               else:
                     import torch
               lowercase__,						lowercase__  =	common_inputs['input_ids'].shape
               # Not using the same length for past_key_values
               lowercase__  =	seqlen + 2
               lowercase__,						lowercase__  =	self.num_layers
               lowercase__,						lowercase__  =	self.num_attention_heads
               lowercase__  =	(
                   batch,
                   num_encoder_attention_heads,
                   past_key_values_length,
                   self._config.hidden_size // num_encoder_attention_heads,
               )

               lowercase__  =	common_inputs['attention_mask'].dtype
               lowercase__  =	torch.cat(
                   [common_inputs['attention_mask'], torch.ones(lowerCAmelCase      ,					lowerCAmelCase      ,					dtype=lowerCAmelCase)]      ,					dim=1)
               lowercase__  =	[
                   (torch.zeros(lowerCAmelCase), torch.zeros(lowerCAmelCase)) for _ in range(lowerCAmelCase)
               ]
         return common_inputs


   def       UpperCAmelCase		(    self	:      Dict      ,					lowerCAmelCase	:      PreTrainedTokenizer      ,					lowerCAmelCase	:      int = -1      ,					lowerCAmelCase	:      int = -1      ,					lowerCAmelCase	:      bool = False      ,					lowerCAmelCase	:      Optional[TensorType] = None      ,					)						->					Mapping[str, Any]:




         """simple docstring"""

         lowercase__  =	compute_effective_axis_dimension(
             lowerCAmelCase      ,					fixed_dimension=OnnxConfig.default_fixed_batch      ,					num_token_to_add=0)

         # If dynamic axis (-1) we forward with a fixed dimension of 8 tokens to avoid optimizations made by ONNX
         lowercase__  =	tokenizer.num_special_tokens_to_add(lowerCAmelCase)
         lowercase__  =	compute_effective_axis_dimension(
             lowerCAmelCase      ,					fixed_dimension=OnnxConfig.default_fixed_sequence      ,					num_token_to_add=lowerCAmelCase)

         # Generate dummy inputs according to compute batch and sequence
         lowercase__  =	[' '.join([tokenizer.unk_token]) * seq_length] * batch_size
         lowercase__  =	dict(tokenizer(lowerCAmelCase      ,					return_tensors=lowerCAmelCase))
         return common_inputs


   def       UpperCAmelCase		(    self	:      str      ,					lowerCAmelCase	:      PreTrainedTokenizer      ,					lowerCAmelCase	:      int = -1      ,					lowerCAmelCase	:      int = -1      ,					lowerCAmelCase	:      bool = False      ,					lowerCAmelCase	:      Optional[TensorType] = None      ,					)						->					Mapping[str, Any]:




         """simple docstring"""

         if self.task in ["default", "seq2seq-lm"]:
               lowercase__  =	self._generate_dummy_inputs_for_default_and_seqaseq_lm(
                   lowerCAmelCase      ,					batch_size=lowerCAmelCase      ,					seq_length=lowerCAmelCase      ,					is_pair=lowerCAmelCase      ,					framework=lowerCAmelCase)

         else:
               lowercase__  =	self._generate_dummy_inputs_for_causal_lm(
                   lowerCAmelCase      ,					batch_size=lowerCAmelCase      ,					seq_length=lowerCAmelCase      ,					is_pair=lowerCAmelCase      ,					framework=lowerCAmelCase)

         return common_inputs


   def       UpperCAmelCase		(    self	:      List[Any]      ,					lowerCAmelCase	:      Optional[int]      ,					lowerCAmelCase	:      Optional[Any]      ,					lowerCAmelCase	:      str      ,					lowerCAmelCase	:      str)						->					Optional[int]:




         """simple docstring"""

         if self.task in ["default", "seq2seq-lm"]:
               lowercase__  =	super()._flatten_past_key_values_(lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase)
         else:
               lowercase__  =	super(lowerCAmelCase      ,					self)._flatten_past_key_values_(
                   lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase      ,					lowerCAmelCase)



   @property
   def       UpperCAmelCase		(    self	:      Optional[int])						->					float:




         """simple docstring"""

         return 1E-4
