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




class        __snake_case	:



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





        '''simple docstring'''





        a__:					List[Any]      							=     []



      def   lowerCamelCase_       (						self   ,      lowercase)     ->      Optional[Any]:





        '''simple docstring'''





        return self.node_position[vertex]



      def   lowerCamelCase_       (						self   ,      lowercase   ,      lowercase)     ->      Optional[int]:





        '''simple docstring'''





        a__:					str      							=     pos



      def   lowerCamelCase_       (						self   ,      lowercase   ,      lowercase   ,      lowercase   ,      lowercase)     ->      int:





        '''simple docstring'''





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

            a__:					Any      							=     self.get_position(positions[smallest_child])
            self.set_position(
                positions[smallest_child]   ,      self.get_position(positions[start]))
            self.set_position(positions[start]   ,      lowercase_)

            self.top_to_bottom(lowercase_   ,      lowercase_   ,      lowercase_   ,      lowercase_)



      def   lowerCamelCase_       (						self   ,      lowercase   ,      lowercase   ,      lowercase   ,      lowercase)     ->      Optional[Any]:





        '''simple docstring'''





        a__:					List[Any]      							=     position[index]

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

          if val < heap[parent]:
            a__:					Any      							=     heap[parent]
            a__:					Tuple      							=     position[parent]
            self.set_position(position[parent]   ,      lowercase_)
          else:
            a__:					Optional[int]      							=     val
            a__:					Tuple      							=     temp
            self.set_position(lowercase_   ,      lowercase_)
            break
          a__:					Dict      							=     parent
        else:
          a__:					Optional[Any]      							=     val
          a__:					Tuple      							=     temp
          self.set_position(lowercase_   ,      0)



      def   lowerCamelCase_       (						self   ,      lowercase   ,      lowercase)     ->      Optional[Any]:





        '''simple docstring'''





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



      def   lowerCamelCase_       (						self   ,      lowercase   ,      lowercase)     ->      Tuple:





        '''simple docstring'''





        a__:					List[str]      							=     positions[0]
        a__:					Dict      							=     sys.maxsize
        self.top_to_bottom(lowercase_   ,      0   ,      len(lowercase_)   ,      lowercase_)
        return temp







def 						__a       (     _SCREAMING_SNAKE_CASE       )     ->Union[str, Any]:
  a__:					Any      							=     Heap()

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

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

  a__:					Tuple      							=     []
  a__:					List[str]      							=     1
  a__:					Tuple      							=     sys.maxsize
  for neighbor, distance in adjacency_list[0]:
    a__:					Dict      							=     0
    a__:					List[Any]      							=     distance
  heap.heapify(__lowerCamelCase		,					__lowerCamelCase       )

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


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

from knapsack import knapsack as k




class        __snake_case	(					unittest.TestCase    ):



      def   lowerCamelCase_       (						self)     ->      Dict:





        '''simple docstring'''





        a__:					List[Any]      							=     0
        a__:					Dict      							=     [0]
        a__:					int      							=     [0]
        a__:					Optional[Any]      							=     len(lowercase)
        self.assertEqual(k.knapsack(lowercase   ,      lowercase   ,      lowercase   ,      lowercase)   ,      0)

        a__:					str      							=     [60]
        a__:					Dict      							=     [10]
        a__:					List[str]      							=     len(lowercase)
        self.assertEqual(k.knapsack(lowercase   ,      lowercase   ,      lowercase   ,      lowercase)   ,      0)



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





        '''simple docstring'''





        a__:					int      							=     3
        a__:					str      							=     [1, 2, 3]
        a__:					Dict      							=     [3, 2, 1]
        a__:					Optional[int]      							=     len(lowercase)
        self.assertEqual(k.knapsack(lowercase   ,      lowercase   ,      lowercase   ,      lowercase)   ,      5)



      def   lowerCamelCase_       (						self)     ->      Union[str, Any]:





        '''simple docstring'''





        a__:					Any      							=     50
        a__:					Optional[int]      							=     [60, 1_00, 1_20]
        a__:					str      							=     [10, 20, 30]
        a__:					int      							=     len(lowercase)
        self.assertEqual(k.knapsack(lowercase   ,      lowercase   ,      lowercase   ,      lowercase)   ,      2_20)


if __name__ == "__main__":
 unittest.main()


