

import sys
from collections import defaultdict

class     __snake_case    :
       """simple docstring"""







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






              """simple docstring"""


              __snake_case       	=							[]


       def 			a		(		self      , _UpperCamelCase   )      ->							Any:






              """simple docstring"""


              return self.node_position[vertex]


       def 			a		(		self      , _UpperCamelCase      , _UpperCamelCase   )      ->							Optional[int]:






              """simple docstring"""


              __snake_case       	=							pos


       def 			a		(		self      , _UpperCamelCase      , _UpperCamelCase      , _UpperCamelCase      , _UpperCamelCase   )      ->							str:






              """simple docstring"""


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

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

                            self.top_to_bottom(_UpperCamelCase      , _UpperCamelCase      , _UpperCamelCase      , _UpperCamelCase   )


       def 			a		(		self      , _UpperCamelCase      , _UpperCamelCase      , _UpperCamelCase      , _UpperCamelCase   )      ->							Dict:






              """simple docstring"""


              __snake_case       	=							position[index]

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

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


       def 			a		(		self      , _UpperCamelCase      , _UpperCamelCase   )      ->							Any:






              """simple docstring"""


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






       def 			a		(		self      , _UpperCamelCase      , _UpperCamelCase   )      ->							Dict:






              """simple docstring"""


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







def 						lowerCamelCase__      ( __A    :List[Any]		):


       """simple docstring"""




       __snake_case       	=							Heap()

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

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

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

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


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




import enum
import os
from hashlib import shaaaa
from typing import Optional

from .. import config
from .logging import get_logger


UpperCamelCase__		 =     get_logger(__name__)

class     __snake_case    (				enum.Enum  ):
       """simple docstring"""







       __SCREAMING_SNAKE_CASE				    =							"all_checks"
       __SCREAMING_SNAKE_CASE				    =							"basic_checks"
       __SCREAMING_SNAKE_CASE				    =							"no_checks"






class     __snake_case    (				snake_case__  ):
       """simple docstring"""













class     __snake_case    (				snake_case__  ):
       """simple docstring"""













class     __snake_case    (				snake_case__  ):
       """simple docstring"""













class     __snake_case    (				snake_case__  ):
       """simple docstring"""














def 						lowerCamelCase__      ( __A    :Optional[dict]	,__A    :dict	,__A    :Any=None		):


       """simple docstring"""




       if expected_checksums is None:
              logger.info("""Unable to verify checksums."""		)
              return
       if len(set(__A		) - set(__A		)		) > 0:
              raise ExpectedMoreDownloadedFiles(str(set(__A		) - set(__A		)		)		)
       if len(set(__A		) - set(__A		)		) > 0:
              raise UnexpectedDownloadedFile(str(set(__A		) - set(__A		)		)		)
       __snake_case       	=							[url for url in expected_checksums if expected_checksums[url] != recorded_checksums[url]]
       __snake_case       	=							""" for """ + verification_name if verification_name is not None else """"""
       if len(__A		) > 0:
              raise NonMatchingChecksumError(
                  F'Checksums didn\'t match{for_verification_name}:\n'
                  F'{bad_urls}\n'
                  """Set `verification_mode='no_checks'` to skip checksums verification and ignore this error"""		)
       logger.info("""All the checksums matched successfully""" + for_verification_name		)

class     __snake_case    (				snake_case__  ):
       """simple docstring"""













class     __snake_case    (				snake_case__  ):
       """simple docstring"""













class     __snake_case    (				snake_case__  ):
       """simple docstring"""













class     __snake_case    (				snake_case__  ):
       """simple docstring"""














def 						lowerCamelCase__      ( __A    :Optional[dict]	,__A    :dict		):


       """simple docstring"""




       if expected_splits is None:
              logger.info("""Unable to verify splits sizes."""		)
              return
       if len(set(__A		) - set(__A		)		) > 0:
              raise ExpectedMoreSplits(str(set(__A		) - set(__A		)		)		)
       if len(set(__A		) - set(__A		)		) > 0:
              raise UnexpectedSplits(str(set(__A		) - set(__A		)		)		)
       __snake_case       	=							[
           {"""expected""": expected_splits[name], """recorded""": recorded_splits[name]}
           for name in expected_splits
           if expected_splits[name].num_examples != recorded_splits[name].num_examples
       ]
       if len(__A		) > 0:
              raise NonMatchingSplitsSizesError(str(__A		)		)
       logger.info("""All the splits matched successfully."""		)







def 						lowerCamelCase__      ( __A    :str	,__A    :bool = True		):


       """simple docstring"""




       if record_checksum:
              __snake_case       	=							shaaaa()
              with open(__A	,"""rb"""		) as f:
                     for chunk in iter(lambda: f.read(1 << 2_0		)	,b""""""		):
                            m.update(__A		)
                     __snake_case       	=							m.hexdigest()
       else:
              __snake_case       	=							None
       return {"num_bytes": os.path.getsize(__A		), "checksum": checksum}







def 						lowerCamelCase__      ( __A    :Optional[int]		):


       """simple docstring"""




       if dataset_size and config.IN_MEMORY_MAX_SIZE:
              return dataset_size < config.IN_MEMORY_MAX_SIZE
       else:
              return False

