





'''simple docstring'''

def 						__magic_name__       (							__UpperCAmelCase							,	__UpperCAmelCase      )						->					bool:

   '''simple docstring'''







   __SCREAMING_SNAKE_CASE      							=       len(SCREAMING_SNAKE_CASE_      )
   __SCREAMING_SNAKE_CASE      							=       [[False] * (required_sum + 1) for _ in range(arr_len + 1      )]

   # for each arr value, a sum of zero(0) can be formed by not taking any element
   # hence True/1
   for i in range(arr_len + 1      ):
      __SCREAMING_SNAKE_CASE      							=       True

   # sum is not zero and set is empty then false
   for i in range(1							,	required_sum + 1      ):
      __SCREAMING_SNAKE_CASE      							=       False

   for i in range(1							,	arr_len + 1      ):
      for j in range(1							,	required_sum + 1      ):
         if arr[i - 1] > j:
            __SCREAMING_SNAKE_CASE      							=       subset[i - 1][j]
         if arr[i - 1] <= j:
            __SCREAMING_SNAKE_CASE      							=       subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]

   return subset[arr_len][required_sum]


if __name__ == "__main__":
    import doctest

    doctest.testmod()












'''simple docstring'''

import sys
from collections import defaultdict







class __a :





   def __init__(					self				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       []





   def      UpperCAmelCase__     (					self				:			List[Any]				,lowerCamelCase				:			List[Any]    ):

      '''simple docstring'''

      return self.node_position[vertex]





   def      UpperCAmelCase__     (					self				:			List[Any]				,lowerCamelCase				:			str				,lowerCamelCase				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       pos





   def      UpperCAmelCase__     (					self				:			List[Any]				,lowerCamelCase				:			Optional[int]				,lowerCamelCase				:			Union[str, Any]				,lowerCamelCase				:			List[Any]				,lowerCamelCase				:			Any    ):

      '''simple docstring'''

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

            __SCREAMING_SNAKE_CASE      							=       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      UpperCAmelCase__     (					self				:			Any				,lowerCamelCase				:			int				,lowerCamelCase				:			List[str]				,lowerCamelCase				:			Optional[Any]				,lowerCamelCase				:			Tuple    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       position[index]

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

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





   def      UpperCAmelCase__     (					self				:			Tuple				,lowerCamelCase				:			List[Any]				,lowerCamelCase				:			List[str]    ):

      '''simple docstring'''

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





   def      UpperCAmelCase__     (					self				:			int				,lowerCamelCase				:			Optional[int]				,lowerCamelCase				:			Dict    ):

      '''simple docstring'''

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





def 						__magic_name__       (							__UpperCAmelCase      )						->					Optional[Any]:

   '''simple docstring'''







   __SCREAMING_SNAKE_CASE      							=       Heap()

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

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

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

   for _ in range(1							,	len(__UpperCAmelCase      )      ):
      __SCREAMING_SNAKE_CASE      							=       heap.delete_minimum(__UpperCAmelCase							,	__UpperCAmelCase      )
      if visited[vertex] == 0:
         tree_edges.append((nbr_tv[vertex], vertex)      )
         __SCREAMING_SNAKE_CASE      							=       1
         for neighbor, distance in adjacency_list[vertex]:
            if (
                visited[neighbor] == 0
                and distance < distance_tv[heap.get_position(__UpperCAmelCase      )]
            ):
               __SCREAMING_SNAKE_CASE      							=       distance
               heap.bottom_to_top(
                   __UpperCAmelCase							,	heap.get_position(__UpperCAmelCase      )							,	__UpperCAmelCase							,	__UpperCAmelCase      )
               __SCREAMING_SNAKE_CASE      							=       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))





