


import sys
from collections import defaultdict



class 							_UpperCamelCase :

   '''simple docstring'''







   def __init__(  self  : List[str]							):






         '''simple docstring'''



         __lowerCamelCase     :      Optional[Any]       						=						[]

   def   _snake_case    (  self  : Optional[int]       ,  _lowerCamelCase  : Tuple							):






         '''simple docstring'''



         return self.node_position[vertex]

   def   _snake_case    (  self  : Optional[int]       ,  _lowerCamelCase  : List[str]       ,  _lowerCamelCase  : Optional[int]							):






         '''simple docstring'''



         __lowerCamelCase     :      Any       						=						pos

   def   _snake_case    (  self  : Optional[int]       ,  _lowerCamelCase  : List[str]       ,  _lowerCamelCase  : Optional[int]       ,  _lowerCamelCase  : List[Any]       ,  _lowerCamelCase  : Tuple							):






         '''simple docstring'''



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

                     __lowerCamelCase     :      Optional[Any]       						=						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   _snake_case    (  self  : int       ,  _lowerCamelCase  : Any       ,  _lowerCamelCase  : Any       ,  _lowerCamelCase  : List[str]       ,  _lowerCamelCase  : Union[str, Any]							):






         '''simple docstring'''



         __lowerCamelCase     :      Any       						=						position[index]

         while index != 0:
               __lowerCamelCase     :      Optional[Any]       						=						int((index - 2) / 2							) if index % 2 == 0 else int((index - 1) / 2							)

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

   def   _snake_case    (  self  : str       ,  _lowerCamelCase  : List[Any]       ,  _lowerCamelCase  : Dict							):






         '''simple docstring'''



         __lowerCamelCase     :      Tuple       						=						len(_lowerCamelCase							) // 2 - 1
         for i in range(_lowerCamelCase       ,  -1       ,  -1							):
               self.top_to_bottom(_lowerCamelCase       ,  _lowerCamelCase       ,  len(_lowerCamelCase							)       ,  _lowerCamelCase							)


   def   _snake_case    (  self  : Optional[int]       ,  _lowerCamelCase  : Dict       ,  _lowerCamelCase  : Any							):






         '''simple docstring'''



         __lowerCamelCase     :      str       						=						positions[0]
         __lowerCamelCase     :      Dict       						=						sys.maxsize
         self.top_to_bottom(_lowerCamelCase       ,  0       ,  len(_lowerCamelCase							)       ,  _lowerCamelCase							)
         return temp





def   _UpperCAmelCase       (     UpperCAmelCase      :			Tuple      ):
      """simple docstring"""




      __lowerCamelCase     :      int       						=						Heap()

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

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

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

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


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







# Copyright 2023 The HuggingFace Team. All rights reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


__UpperCamelCase    :						Any     =							{
    'configuration_mgp_str': ['MGP_STR_PRETRAINED_CONFIG_ARCHIVE_MAP', 'MgpstrConfig'],
    'processing_mgp_str': ['MgpstrProcessor'],
    'tokenization_mgp_str': ['MgpstrTokenizer'],
}

try:
    if not is_torch_available():
        raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
    pass
else:
    __UpperCamelCase    :						Tuple     =							[
        'MGP_STR_PRETRAINED_MODEL_ARCHIVE_LIST',
        'MgpstrModel',
        'MgpstrPreTrainedModel',
        'MgpstrForSceneTextRecognition',
    ]

if TYPE_CHECKING:
    from .configuration_mgp_str import MGP_STR_PRETRAINED_CONFIG_ARCHIVE_MAP, MgpstrConfig
    from .processing_mgp_str import MgpstrProcessor
    from .tokenization_mgp_str import MgpstrTokenizer

    try:
        if not is_torch_available():
            raise OptionalDependencyNotAvailable()
    except OptionalDependencyNotAvailable:
        pass
    else:
        from .modeling_mgp_str import (
            MGP_STR_PRETRAINED_MODEL_ARCHIVE_LIST,
            MgpstrForSceneTextRecognition,
            MgpstrModel,
            MgpstrPreTrainedModel,
        )
else:
    import sys

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



