'''simple docstring'''
import sys
from collections import defaultdict






class 			__lowercase		:







     """simple docstring"""






     def __init__(		self    ):
         __UpperCamelCase	:	Any		    =  []







     def lowerCAmelCase     (		self     ,			_lowerCamelCase    ):
         return self.node_position[vertex]







     def lowerCAmelCase     (		self     ,			_lowerCamelCase     ,			_lowerCamelCase    ):
         __UpperCamelCase	:	Optional[int]		    =  pos







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

                 __UpperCamelCase	:	str		    =  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 lowerCAmelCase     (		self     ,			_lowerCamelCase     ,			_lowerCamelCase     ,			_lowerCamelCase     ,			_lowerCamelCase    ):
         __UpperCamelCase	:	Dict		    =  position[index]

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

             if val < heap[parent]:
                 __UpperCamelCase	:	Optional[int]		    =  heap[parent]
                 __UpperCamelCase	:	Optional[Any]		    =  position[parent]
                 self.set_position(position[parent]     ,			_lowerCamelCase    )
             else:
                 __UpperCamelCase	:	str		    =  val
                 __UpperCamelCase	:	Optional[int]		    =  temp
                 self.set_position(_lowerCamelCase     ,			_lowerCamelCase    )
                 break
             __UpperCamelCase	:	Any		    =  parent
         else:
             __UpperCamelCase	:	List[str]		    =  val
             __UpperCamelCase	:	List[Any]		    =  temp
             self.set_position(_lowerCamelCase     ,			0    )







     def lowerCAmelCase     (		self     ,			_lowerCamelCase     ,			_lowerCamelCase    ):
         __UpperCamelCase	:	Dict		    =  len(_lowerCamelCase    ) // 2 - 1
         for i in range(_lowerCamelCase     ,			-1     ,			-1    ):
             self.top_to_bottom(_lowerCamelCase     ,			_lowerCamelCase     ,			len(_lowerCamelCase    )     ,			_lowerCamelCase    )







     def lowerCAmelCase     (		self     ,			_lowerCamelCase     ,			_lowerCamelCase    ):
         __UpperCamelCase	:	Union[str, Any]		    =  positions[0]
         __UpperCamelCase	:	List[str]		    =  sys.maxsize
         self.top_to_bottom(_lowerCamelCase     ,			0     ,			len(_lowerCamelCase    )     ,			_lowerCamelCase    )
         return temp







def  _UpperCamelCase (     _a	:	int			):




    """simple docstring"""



    __UpperCamelCase	:	List[Any]		    =  Heap()

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

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

    __UpperCamelCase	:	Tuple		    =  []
    __UpperCamelCase	:	Dict		    =  1
    __UpperCamelCase	:	int		    =  sys.maxsize
    for neighbor, distance in adjacency_list[0]:
        __UpperCamelCase	:	Dict		    =  0
        __UpperCamelCase	:	Tuple		    =  distance
    heap.heapify(_a				,     _a			)

    for _ in range(1				,     len(_a			)			):
        __UpperCamelCase	:	Optional[int]		    =  heap.delete_minimum(_a				,     _a			)
        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(_a			)]
                ):
                    __UpperCamelCase	:	Union[str, Any]		    =  distance
                    heap.bottom_to_top(
                        _a				,     heap.get_position(_a			)				,     _a				,     _a			)
                    __UpperCamelCase	:	str		    =  vertex
    return tree_edges


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

from ...feature_extraction_utils import BatchFeature, FeatureExtractionMixin
from ...utils import is_bsa_available, logging, requires_backends


if is_bsa_available():
  import bsa
  from bsa import BeautifulSoup


a=  logging.get_logger(__name__)






class 			__lowercase		(						_lowerCamelCase						):







     """simple docstring"""






     def __init__(		self     ,			**_lowerCamelCase    ):
         requires_backends(self     ,			['bs4']    )
         super().__init__(**_lowerCamelCase    )







     def lowerCAmelCase     (		self     ,			_lowerCamelCase    ):
         __UpperCamelCase	:	str		    =  []
         __UpperCamelCase	:	Dict		    =  []
         __UpperCamelCase	:	Union[str, Any]		    =  element if element.name else element.parent
         for parent in child.parents:  # type: bs4.element.Tag
             __UpperCamelCase	:	str		    =  parent.find_all(child.name     ,			recursive=_lowerCamelCase    )
             xpath_tags.append(child.name    )
             xpath_subscripts.append(
                 0 if 1 == len(_lowerCamelCase    ) else next(i for i, s in enumerate(_lowerCamelCase     ,			1    ) if s is child    )    )
             __UpperCamelCase	:	Union[str, Any]		    =  parent
         xpath_tags.reverse()
         xpath_subscripts.reverse()
         return xpath_tags, xpath_subscripts







     def lowerCAmelCase     (		self     ,			_lowerCamelCase    ):
         __UpperCamelCase	:	List[str]		    =  BeautifulSoup(_lowerCamelCase     ,			'html.parser'    )

         __UpperCamelCase	:	int		    =  []
         __UpperCamelCase	:	List[Any]		    =  []
         __UpperCamelCase	:	int		    =  []

         for element in html_code.descendants:
             if type(_lowerCamelCase    ) == bsa.element.NavigableString:
                 if type(element.parent    ) != bsa.element.Tag:
                     continue

                 __UpperCamelCase	:	Tuple		    =  html.unescape(_lowerCamelCase    ).strip()
                 if not text_in_this_tag:
                     continue

                 all_doc_strings.append(_lowerCamelCase    )

                 __UpperCamelCase    ,					__UpperCamelCase	:	Union[str, Any]		    =  self.xpath_soup(_lowerCamelCase    )
                 stringaxtag_seq.append(_lowerCamelCase    )
                 stringaxsubs_seq.append(_lowerCamelCase    )

         if len(_lowerCamelCase    ) != len(_lowerCamelCase    ):
             raise ValueError('Number of doc strings and xtags does not correspond'    )
         if len(_lowerCamelCase    ) != len(_lowerCamelCase    ):
             raise ValueError('Number of doc strings and xsubs does not correspond'    )

         return all_doc_strings, stringaxtag_seq, stringaxsubs_seq







     def lowerCAmelCase     (		self     ,			_lowerCamelCase     ,			_lowerCamelCase    ):
         __UpperCamelCase	:	Dict		    =  ''
         for tagname, subs in zip(_lowerCamelCase     ,			_lowerCamelCase    ):
             xpath += f"""/{tagname}"""
             if subs != 0:
                 xpath += f"""[{subs}]"""
         return xpath







     def __call__(		self     ,			_lowerCamelCase    ):
         __UpperCamelCase	:	List[Any]		    =  False

         # Check that strings has a valid type
         if isinstance(_lowerCamelCase     ,			_lowerCamelCase    ):
             __UpperCamelCase	:	List[str]		    =  True
         elif isinstance(_lowerCamelCase     ,			(list, tuple)    ):
             if len(_lowerCamelCase    ) == 0 or isinstance(html_strings[0]     ,			_lowerCamelCase    ):
                 __UpperCamelCase	:	Optional[int]		    =  True

         if not valid_strings:
             raise ValueError(
                 'HTML strings must of type `str`, `List[str]` (batch of examples), '
                 f"""but is of type {type(_lowerCamelCase    )}."""    )

         __UpperCamelCase	:	Dict		    =  bool(isinstance(_lowerCamelCase     ,			(list, tuple)    ) and (isinstance(html_strings[0]     ,			_lowerCamelCase    ))    )

         if not is_batched:
             __UpperCamelCase	:	Tuple		    =  [html_strings]

         # Get nodes + xpaths
         __UpperCamelCase	:	Tuple		    =  []
         __UpperCamelCase	:	Tuple		    =  []
         for html_string in html_strings:
             __UpperCamelCase    ,					__UpperCamelCase    ,					__UpperCamelCase	:	str		    =  self.get_three_from_single(_lowerCamelCase    )
             nodes.append(_lowerCamelCase    )
             __UpperCamelCase	:	Union[str, Any]		    =  []
             for node, tag_list, sub_list in zip(_lowerCamelCase     ,			_lowerCamelCase     ,			_lowerCamelCase    ):
                 __UpperCamelCase	:	Optional[Any]		    =  self.construct_xpath(_lowerCamelCase     ,			_lowerCamelCase    )
                 xpath_strings.append(_lowerCamelCase    )
             xpaths.append(_lowerCamelCase    )

         # return as Dict
         __UpperCamelCase	:	Optional[int]		    =  {'nodes': nodes, 'xpaths': xpaths}
         __UpperCamelCase	:	Union[str, Any]		    =  BatchFeature(data=_lowerCamelCase     ,			tensor_type=_lowerCamelCase    )

         return encoded_inputs



