

'''simple docstring'''






import os
from shutil import copyfile
from typing import List, Optional, Tuple

from ...tokenization_utils import AddedToken
from ...tokenization_utils_fast import PreTrainedTokenizerFast
from ...utils import is_sentencepiece_available, logging


if is_sentencepiece_available():
 from .tokenization_big_bird import BigBirdTokenizer
else:
 lowerCAmelCase__   		=      None

lowerCAmelCase__   		=      logging.get_logger(__name__)
lowerCAmelCase__   		=      {'''vocab_file''': '''spiece.model''', '''tokenizer_file''': '''tokenizer.json'''}

lowerCAmelCase__   		=      {
    '''vocab_file''': {
        '''google/bigbird-roberta-base''': '''https://huggingface.co/google/bigbird-roberta-base/resolve/main/spiece.model''',
        '''google/bigbird-roberta-large''': (
            '''https://huggingface.co/google/bigbird-roberta-large/resolve/main/spiece.model'''
        ),
        '''google/bigbird-base-trivia-itc''': (
            '''https://huggingface.co/google/bigbird-base-trivia-itc/resolve/main/spiece.model'''
        ),
    },
    '''tokenizer_file''': {
        '''google/bigbird-roberta-base''': (
            '''https://huggingface.co/google/bigbird-roberta-base/resolve/main/tokenizer.json'''
        ),
        '''google/bigbird-roberta-large''': (
            '''https://huggingface.co/google/bigbird-roberta-large/resolve/main/tokenizer.json'''
        ),
        '''google/bigbird-base-trivia-itc''': (
            '''https://huggingface.co/google/bigbird-base-trivia-itc/resolve/main/tokenizer.json'''
        ),
    },
}

lowerCAmelCase__   		=      {
    '''google/bigbird-roberta-base''': 4096,
    '''google/bigbird-roberta-large''': 4096,
    '''google/bigbird-base-trivia-itc''': 4096,
}


lowerCAmelCase__   		=      '''▁'''






class      lowercase_      (lowerCamelCase__ ):




  """simple docstring"""




  SCREAMING_SNAKE_CASE       :    int							     =     VOCAB_FILES_NAMES
  SCREAMING_SNAKE_CASE       :    Union[str, Any]							     =     PRETRAINED_VOCAB_FILES_MAP
  SCREAMING_SNAKE_CASE       :    str							     =     PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
  SCREAMING_SNAKE_CASE       :    Union[str, Any]							     =     BigBirdTokenizer
  SCREAMING_SNAKE_CASE       :    Optional[Any]							     =     ['input_ids', 'attention_mask']
  SCREAMING_SNAKE_CASE       :    List[int]							     =     []






  def __init__( self  :	Union[str, Any]   ,lowercase__  :	str=None   ,lowercase__  :	List[str]=None   ,lowercase__  :	Dict="<unk>"   ,lowercase__  :	Dict="<s>"   ,lowercase__  :	Tuple="</s>"   ,lowercase__  :	int="<pad>"   ,lowercase__  :	Optional[Any]="[SEP]"   ,lowercase__  :	List[str]="[MASK]"   ,lowercase__  :	Tuple="[CLS]"   ,**lowercase__  :	List[str]   ,):
   __lowercase				    =					AddedToken(lowercase__   ,lstrip=lowercase__   ,rstrip=lowercase__     ) if isinstance(lowercase__   ,lowercase__     ) else bos_token
   __lowercase				    =					AddedToken(lowercase__   ,lstrip=lowercase__   ,rstrip=lowercase__     ) if isinstance(lowercase__   ,lowercase__     ) else eos_token
   __lowercase				    =					AddedToken(lowercase__   ,lstrip=lowercase__   ,rstrip=lowercase__     ) if isinstance(lowercase__   ,lowercase__     ) else unk_token
   __lowercase				    =					AddedToken(lowercase__   ,lstrip=lowercase__   ,rstrip=lowercase__     ) if isinstance(lowercase__   ,lowercase__     ) else pad_token
   __lowercase				    =					AddedToken(lowercase__   ,lstrip=lowercase__   ,rstrip=lowercase__     ) if isinstance(lowercase__   ,lowercase__     ) else cls_token
   __lowercase				    =					AddedToken(lowercase__   ,lstrip=lowercase__   ,rstrip=lowercase__     ) if isinstance(lowercase__   ,lowercase__     ) else sep_token

   # Mask token behave like a normal word, i.e. include the space before it
   __lowercase				    =					AddedToken(lowercase__   ,lstrip=lowercase__   ,rstrip=lowercase__     ) if isinstance(lowercase__   ,lowercase__     ) else mask_token

   super().__init__(
       lowercase__   ,tokenizer_file=lowercase__   ,bos_token=lowercase__   ,eos_token=lowercase__   ,unk_token=lowercase__   ,sep_token=lowercase__   ,pad_token=lowercase__   ,cls_token=lowercase__   ,mask_token=lowercase__   ,**lowercase__   ,)

   __lowercase				    =					vocab_file
   __lowercase				    =					False if not self.vocab_file else True






  def    SCREAMING_SNAKE_CASE ( self  :	List[Any]   ,lowercase__  :	List[int]   ,lowercase__  :	Optional[List[int]] = None     ):
   __lowercase				    =					[self.sep_token_id]
   __lowercase				    =					[self.cls_token_id]
   if token_ids_a is None:
    return cls + token_ids_a + sep
   return cls + token_ids_a + sep + token_ids_a + sep






  def    SCREAMING_SNAKE_CASE ( self  :	Tuple   ,lowercase__  :	List[int]   ,lowercase__  :	Optional[List[int]] = None   ,lowercase__  :	bool = False     ):

   if already_has_special_tokens:
    if token_ids_a is not None:
     raise ValueError(
         '''You should not supply a second sequence if the provided sequence of '''
         '''ids is already formatted with special tokens for the model.'''     )
    return [1 if x in [self.sep_token_id, self.cls_token_id] else 0 for x in token_ids_a]

   if token_ids_a is None:
    return [1] + ([0] * len(lowercase__     )) + [1]
   return [1] + ([0] * len(lowercase__     )) + [1] + ([0] * len(lowercase__     )) + [1]






  def    SCREAMING_SNAKE_CASE ( self  :	List[Any]   ,lowercase__  :	List[int]   ,lowercase__  :	Optional[List[int]] = None     ):
   __lowercase				    =					[self.sep_token_id]
   __lowercase				    =					[self.cls_token_id]

   if token_ids_a is None:
    return len(cls + token_ids_a + sep     ) * [0]
   return len(cls + token_ids_a + sep     ) * [0] + len(token_ids_a + sep     ) * [1]






  def    SCREAMING_SNAKE_CASE ( self  :	int   ,lowercase__  :	str   ,lowercase__  :	Optional[str] = None     ):
   if not self.can_save_slow_tokenizer:
    raise ValueError(
        '''Your fast tokenizer does not have the necessary information to save the vocabulary for a slow '''
        '''tokenizer.'''     )

   if not os.path.isdir(lowercase__     ):
    logger.error(F"Vocabulary path ({save_directory}) should be a directory"     )
    return
   __lowercase				    =					os.path.join(
       lowercase__   ,(filename_prefix + '''-''' if filename_prefix else '''''') + VOCAB_FILES_NAMES['''vocab_file''']     )

   if os.path.abspath(self.vocab_file     ) != os.path.abspath(lowercase__     ):
    copyfile(self.vocab_file   ,lowercase__     )

   return (out_vocab_file,)


import sys
from collections import defaultdict
class     lowerCAmelCase_     :







							def __init__(   self      :     Optional[int]		):
												_UpperCamelCase			     =     []







							def  UpperCamelCase_						(   self      :     Any ,			_A      :     str		):
												return self.node_position[vertex]







							def  UpperCamelCase_						(   self      :     Optional[Any] ,			_A      :     List[str] ,			_A      :     Union[str, Any]		):
												_UpperCamelCase			     =     pos







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

																						_UpperCamelCase			     =     self.get_position(positions[smallest_child]		)
																						self.set_position(
																						    positions[smallest_child] ,			self.get_position(positions[start]		)		)
																						self.set_position(positions[start] ,			_A		)

																						self.top_to_bottom(_A ,			_A ,			_A ,			_A		)







							def  UpperCamelCase_						(   self      :     List[str] ,			_A      :     Tuple ,			_A      :     Optional[Any] ,			_A      :     int ,			_A      :     Optional[int]		):
												_UpperCamelCase			     =     position[index]

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

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







							def  UpperCamelCase_						(   self      :     int ,			_A      :     Tuple ,			_A      :     int		):
												_UpperCamelCase			     =     len(_A		) // 2 - 1
												for i in range(_A ,			-1 ,			-1		):
																	self.top_to_bottom(_A ,			_A ,			len(_A		) ,			_A		)







							def  UpperCamelCase_						(   self      :     Any ,			_A      :     int ,			_A      :     List[str]		):
												_UpperCamelCase			     =     positions[0]
												_UpperCamelCase			     =     sys.maxsize
												self.top_to_bottom(_A ,			0 ,			len(_A		) ,			_A		)
												return temp




def 					_snake_case	(  __snake_case						):
					_UpperCamelCase			     =     Heap()

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

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

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

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


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