



"""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						)  ->      Optional[Any]:





    '''simple docstring'''




    return self.node_position[vertex]

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





    '''simple docstring'''




    UpperCAmelCase	:					int	=	pos

   def 	SCREAMING_SNAKE_CASE     (   self      ,     _SCREAMING_SNAKE_CASE      ,     _SCREAMING_SNAKE_CASE      ,     _SCREAMING_SNAKE_CASE      ,     _SCREAMING_SNAKE_CASE						)  ->      Optional[int]:





    '''simple docstring'''




    if start > size // 2 - 1:
     return
    else:
     if 2 * start + 2 >= size:
      UpperCAmelCase	:					Dict	=	2 * start + 1
     else:
      if heap[2 * start + 1] < heap[2 * start + 2]:
       UpperCAmelCase	:					Union[str, Any]	=	2 * start + 1
      else:
       UpperCAmelCase	:					Union[str, Any]	=	2 * start + 2
     if heap[smallest_child] < heap[start]:
      UpperCAmelCase	,		UpperCAmelCase	:					List[Any]	=	heap[smallest_child], positions[smallest_child]
      UpperCAmelCase	,		UpperCAmelCase	:					str	=	(
          heap[start],
          positions[start],
      )
      UpperCAmelCase	,		UpperCAmelCase	:					Union[str, Any]	=	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						)  ->      str:





    '''simple docstring'''




    UpperCAmelCase	:					str	=	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	:					List[str]	=	heap[parent]
      UpperCAmelCase	:					Dict	=	position[parent]
      self.set_position(position[parent]      ,     _SCREAMING_SNAKE_CASE						)
     else:
      UpperCAmelCase	:					int	=	val
      UpperCAmelCase	:					List[Any]	=	temp
      self.set_position(_SCREAMING_SNAKE_CASE      ,     _SCREAMING_SNAKE_CASE						)
      break
     UpperCAmelCase	:					Any	=	parent
    else:
     UpperCAmelCase	:					List[str]	=	val
     UpperCAmelCase	:					List[Any]	=	temp
     self.set_position(_SCREAMING_SNAKE_CASE      ,     0						)

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





    '''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	:					str	=	positions[0]
    UpperCAmelCase	:					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	:					int	=	Heap()

 UpperCAmelCase	:					Any	=	[0] * len(UpperCamelCase						)
 UpperCAmelCase	:					Union[str, Any]	=	[-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[Any]	=	[]  # Heap of Distance of vertices from their neighboring vertex
 UpperCAmelCase	:					str	=	[]

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

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

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


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

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_tf_available, is_torch_available


A:   Optional[Any]								=		{
    "configuration_tapas": ["TAPAS_PRETRAINED_CONFIG_ARCHIVE_MAP", "TapasConfig"],
    "tokenization_tapas": ["TapasTokenizer"],
}

try:
      if not is_torch_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      A:   Optional[int]								=		[
          "TAPAS_PRETRAINED_MODEL_ARCHIVE_LIST",
          "TapasForMaskedLM",
          "TapasForQuestionAnswering",
          "TapasForSequenceClassification",
          "TapasModel",
          "TapasPreTrainedModel",
          "load_tf_weights_in_tapas",
      ]
try:
      if not is_tf_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      A:   List[str]								=		[
          "TF_TAPAS_PRETRAINED_MODEL_ARCHIVE_LIST",
          "TFTapasForMaskedLM",
          "TFTapasForQuestionAnswering",
          "TFTapasForSequenceClassification",
          "TFTapasModel",
          "TFTapasPreTrainedModel",
      ]


if TYPE_CHECKING:
      from .configuration_tapas import TAPAS_PRETRAINED_CONFIG_ARCHIVE_MAP, TapasConfig
      from .tokenization_tapas import TapasTokenizer

      try:
            if not is_torch_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .modeling_tapas import (
                TAPAS_PRETRAINED_MODEL_ARCHIVE_LIST,
                TapasForMaskedLM,
                TapasForQuestionAnswering,
                TapasForSequenceClassification,
                TapasModel,
                TapasPreTrainedModel,
                load_tf_weights_in_tapas,
            )

      try:
            if not is_tf_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .modeling_tf_tapas import (
                TF_TAPAS_PRETRAINED_MODEL_ARCHIVE_LIST,
                TFTapasForMaskedLM,
                TFTapasForQuestionAnswering,
                TFTapasForSequenceClassification,
                TFTapasModel,
                TFTapasPreTrainedModel,
            )


else:
      import sys

      A:   Optional[Any]								=		_LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)
