



"""simple docstring"""
import sys
from collections import defaultdict



class    SCREAMING_SNAKE_CASE__						:

   def __init__(     self		)						->   str:





    '''simple docstring'''




    UpperCAmelCase			:      Optional[int]			=			[]

   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE		)						->   Dict:





    '''simple docstring'''




    return self.node_position[vertex]

   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)						->   int:





    '''simple docstring'''




    UpperCAmelCase			:      Tuple			=			pos

   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)						->   Dict:





    '''simple docstring'''




    if start > size // 2 - 1:
     return
    else:
     if 2 * start + 2 >= size:
      UpperCAmelCase			:      Any			=			2 * start + 1
     else:
      if heap[2 * start + 1] < heap[2 * start + 2]:
       UpperCAmelCase			:      int			=			2 * start + 1
      else:
       UpperCAmelCase			:      Tuple			=			2 * start + 2
     if heap[smallest_child] < heap[start]:
      UpperCAmelCase			:      List[Any]			=			heap[smallest_child], positions[smallest_child]
      UpperCAmelCase			:      int			=			(
          heap[start],
          positions[start],
      )
      UpperCAmelCase			:      Dict			=			temp, tempa

      UpperCAmelCase			:      List[Any]			=			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 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)						->   Optional[int]:





    '''simple docstring'''




    UpperCAmelCase			:      List[Any]			=			position[index]

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

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

   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)						->   Dict:





    '''simple docstring'''




    UpperCAmelCase			:      Tuple			=			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 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE   ,  _SCREAMING_SNAKE_CASE		)						->   int:





    '''simple docstring'''




    UpperCAmelCase			:      Dict			=			positions[0]
    UpperCAmelCase			:      List[Any]			=			sys.maxsize
    self.top_to_bottom(_SCREAMING_SNAKE_CASE   ,  0   ,  len(_SCREAMING_SNAKE_CASE		)   ,  _SCREAMING_SNAKE_CASE		)
    return temp

def    _snake_case		(		UpperCamelCase		:	Tuple		):
 UpperCAmelCase			:      List[str]			=			Heap()

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

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

 UpperCAmelCase			:      Optional[int]			=			[]
 UpperCAmelCase			:      Optional[int]			=			1
 UpperCAmelCase			:      Dict			=			sys.maxsize
 for neighbor, distance in adjacency_list[0]:
  UpperCAmelCase			:      Any			=			0
  UpperCAmelCase			:      List[Any]			=			distance
 heap.heapify(UpperCamelCase    ,	UpperCamelCase		)

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


if __name__ == "__main__":  # pragma: no cover
      # < --------- Prims Algorithm --------- >
      A:     Optional[Any]										=	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"""
import os
import unittest

from transformers.models.transfo_xl.tokenization_transfo_xl import VOCAB_FILES_NAMES, TransfoXLTokenizer

from ...test_tokenization_common import TokenizerTesterMixin



class    SCREAMING_SNAKE_CASE__						(      UpperCAmelCase__   ,    unittest.TestCase				):
   __lowerCAmelCase						:     List[Any]		=		TransfoXLTokenizer
   __lowerCAmelCase						:     Optional[int]		=		False
   __lowerCAmelCase						:     Optional[Any]		=		False

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   List[str]:





    '''simple docstring'''




    super().setUp()

    UpperCAmelCase			:      Optional[Any]			=			[
        """<unk>""",
        """[CLS]""",
        """[SEP]""",
        """want""",
        """unwanted""",
        """wa""",
        """un""",
        """running""",
        """,""",
        """low""",
        """l""",
    ]
    UpperCAmelCase			:      int			=			os.path.join(self.tmpdirname   ,  VOCAB_FILES_NAMES["""vocab_file"""]		)
    with open(self.vocab_file   ,  """w"""   ,  encoding="""utf-8"""		) as vocab_writer:
     vocab_writer.write("""""".join([x + """\n""" for x in vocab_tokens]		)		)

   def 			SCREAMING_SNAKE_CASE  (     self   ,  **_SCREAMING_SNAKE_CASE		)						->   List[Any]:





    '''simple docstring'''




    UpperCAmelCase			:      Optional[Any]			=			True
    return TransfoXLTokenizer.from_pretrained(self.tmpdirname   ,  **_SCREAMING_SNAKE_CASE		)

   def 			SCREAMING_SNAKE_CASE  (     self   ,  _SCREAMING_SNAKE_CASE		)						->   List[Any]:





    '''simple docstring'''




    UpperCAmelCase			:      int			=			"""<unk> UNwanted , running"""
    UpperCAmelCase			:      Dict			=			"""<unk> unwanted, running"""
    return input_text, output_text

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Any:





    '''simple docstring'''




    UpperCAmelCase			:      List[str]			=			TransfoXLTokenizer(vocab_file=self.vocab_file   ,  lower_case=_SCREAMING_SNAKE_CASE		)

    UpperCAmelCase			:      Dict			=			tokenizer.tokenize("""<unk> UNwanted , running"""		)
    self.assertListEqual(_SCREAMING_SNAKE_CASE   ,  ["""<unk>""", """unwanted""", """,""", """running"""]		)

    self.assertListEqual(tokenizer.convert_tokens_to_ids(_SCREAMING_SNAKE_CASE		)   ,  [0, 4, 8, 7]		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Tuple:





    '''simple docstring'''




    UpperCAmelCase			:      Tuple			=			TransfoXLTokenizer(lower_case=_SCREAMING_SNAKE_CASE		)

    self.assertListEqual(
        tokenizer.tokenize(""" \tHeLLo ! how  \n Are yoU ?  """		)   ,  ["""hello""", """!""", """how""", """are""", """you""", """?"""]		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Optional[Any]:





    '''simple docstring'''




    UpperCAmelCase			:      Optional[Any]			=			TransfoXLTokenizer(lower_case=_SCREAMING_SNAKE_CASE		)

    self.assertListEqual(
        tokenizer.tokenize(""" \tHeLLo ! how  \n Are yoU ?  """		)   ,  ["""HeLLo""", """!""", """how""", """Are""", """yoU""", """?"""]		)

   def 			SCREAMING_SNAKE_CASE  (     self		)						->   int:





    '''simple docstring'''




    UpperCAmelCase			:      List[Any]			=			TransfoXLTokenizer(lower_case=_SCREAMING_SNAKE_CASE		)
    UpperCAmelCase			:      Dict			=			"""Hello (bracket) and side-scrolled [and] Henry's $5,000 with 3.34 m. What's up!?"""
    UpperCAmelCase			:      Optional[Any]			=			[
        """Hello""",
        """(""",
        """bracket""",
        """)""",
        """and""",
        """side""",
        """@-@""",
        """scrolled""",
        """[""",
        """and""",
        """]""",
        """Henry""",
        """'s""",
        """$""",
        """5""",
        """@,@""",
        """000""",
        """with""",
        """3""",
        """@.@""",
        """34""",
        """m""",
        """.""",
        """What""",
        """'s""",
        """up""",
        """!""",
        """?""",
    ]

    self.assertListEqual(tokenizer.tokenize(_SCREAMING_SNAKE_CASE		)   ,  _SCREAMING_SNAKE_CASE		)

    self.assertEqual(tokenizer.convert_tokens_to_string(_SCREAMING_SNAKE_CASE		)   ,  _SCREAMING_SNAKE_CASE		)




   def 			SCREAMING_SNAKE_CASE  (     self		)						->   Dict:





    '''simple docstring'''




    UpperCAmelCase			:      List[str]			=			self.get_tokenizer()
    UpperCAmelCase			:      Tuple			=			len(_SCREAMING_SNAKE_CASE		)

    tokenizer.add_tokens(["""new1""", """new2"""]		)
    tokenizer.move_added_token("""new1"""   ,  1		)

    # Check that moved token is not copied (duplicate)
    self.assertEqual(len(_SCREAMING_SNAKE_CASE		)   ,  original_len + 2		)
    # Check that token is moved to specified id
    self.assertEqual(tokenizer.encode("""new1"""		)   ,  [1]		)
    self.assertEqual(tokenizer.decode([1]		)   ,  """new1"""		)
