


from typing import Dict, List, Optional, Union

import numpy as np

from ...image_processing_utils import BaseImageProcessor, BatchFeature, get_size_dict
from ...image_transforms import (
    center_crop,
    convert_to_rgb,
    get_resize_output_image_size,
    normalize,
    rescale,
    resize,
    to_channel_dimension_format,
)
from ...image_utils import (
    OPENAI_CLIP_MEAN,
    OPENAI_CLIP_STD,
    ChannelDimension,
    ImageInput,
    PILImageResampling,
    make_list_of_images,
    to_numpy_array,
    valid_images,
)
from ...utils import TensorType, is_vision_available, logging


A      :    List[str]		=					logging.get_logger(__name__)


if is_vision_available():
    import PIL







class 			_lowercase (							__lowerCamelCase):


       """simple docstring"""




       A__											=			["""pixel_values"""]





       def __init__(   self							:			Dict					,      __lowerCamelCase							:			Optional[int] = True					,      __lowerCamelCase							:			List[str] = None					,      __lowerCamelCase							:			Tuple = PILImageResampling.BICUBIC					,      __lowerCamelCase							:			Dict = True					,      __lowerCamelCase							:			str = None					,      __lowerCamelCase							:			Union[str, Any] = True					,      __lowerCamelCase							:			Tuple = 1 / 255					,      __lowerCamelCase							:			Optional[int] = True					,      __lowerCamelCase							:			int = None					,      __lowerCamelCase							:			List[str] = None					,      __lowerCamelCase							:			Any = True					,      **__lowerCamelCase							:			List[str]					,      ):


             '''simple docstring'''



             super().__init__(**__lowerCamelCase       )
             lowerCamelCase__		:				Optional[int]    =  size if size is not None else {"shortest_edge": 224}
             lowerCamelCase__		:				Tuple    =  get_size_dict(__lowerCamelCase					,      default_to_square=__lowerCamelCase       )
             lowerCamelCase__		:				Optional[Any]    =  crop_size if crop_size is not None else {"height": 224, "width": 224}
             lowerCamelCase__		:				Union[str, Any]    =  get_size_dict(__lowerCamelCase					,      default_to_square=__lowerCamelCase					,      param_name="crop_size"       )

             lowerCamelCase__		:				Union[str, Any]    =  do_resize
             lowerCamelCase__		:				Dict    =  size
             lowerCamelCase__		:				int    =  resample
             lowerCamelCase__		:				Tuple    =  do_center_crop
             lowerCamelCase__		:				Dict    =  crop_size
             lowerCamelCase__		:				List[str]    =  do_rescale
             lowerCamelCase__		:				Tuple    =  rescale_factor
             lowerCamelCase__		:				Optional[Any]    =  do_normalize
             lowerCamelCase__		:				List[Any]    =  image_mean if image_mean is not None else OPENAI_CLIP_MEAN
             lowerCamelCase__		:				str    =  image_std if image_std is not None else OPENAI_CLIP_STD
             lowerCamelCase__		:				Any    =  do_convert_rgb





       def 						lowerCAmelCase     (   self							:			List[Any]					,      __lowerCamelCase							:			str					,      __lowerCamelCase							:			List[Any]					,      __lowerCamelCase							:			Tuple = PILImageResampling.BICUBIC					,      __lowerCamelCase							:			Optional[int] = None					,      **__lowerCamelCase							:			Optional[int]					,      ):


             '''simple docstring'''



             lowerCamelCase__		:				Optional[Any]    =  get_size_dict(__lowerCamelCase					,      default_to_square=__lowerCamelCase       )
             if "shortest_edge" not in size:
                   raise ValueError(f"The `size` parameter must contain the key `shortest_edge`. Got {size.keys()}"       )
             lowerCamelCase__		:				Optional[int]    =  get_resize_output_image_size(__lowerCamelCase					,      size=size["shortest_edge"]					,      default_to_square=__lowerCamelCase       )
             return resize(__lowerCamelCase					,      size=__lowerCamelCase					,      resample=__lowerCamelCase					,      data_format=__lowerCamelCase					,      **__lowerCamelCase       )





       def 						lowerCAmelCase     (   self							:			int					,      __lowerCamelCase							:			str					,      __lowerCamelCase							:			Union[str, Any]					,      __lowerCamelCase							:			List[str] = None					,      **__lowerCamelCase							:			Any					,      ):


             '''simple docstring'''



             lowerCamelCase__		:				Any    =  get_size_dict(__lowerCamelCase       )
             if "height" not in size or "width" not in size:
                   raise ValueError(f"The `size` parameter must contain the keys (height, width). Got {size.keys()}"       )
             return center_crop(__lowerCamelCase					,      size=(size["height"], size["width"])					,      data_format=__lowerCamelCase					,      **__lowerCamelCase       )





       def 						lowerCAmelCase     (   self							:			Any					,      __lowerCamelCase							:			int					,      __lowerCamelCase							:			Union[str, Any]					,      __lowerCamelCase							:			Optional[Any] = None					,      **__lowerCamelCase							:			Tuple					,      ):


             '''simple docstring'''



             return rescale(__lowerCamelCase					,      scale=__lowerCamelCase					,      data_format=__lowerCamelCase					,      **__lowerCamelCase       )





       def 						lowerCAmelCase     (   self							:			List[str]					,      __lowerCamelCase							:			Optional[int]					,      __lowerCamelCase							:			str					,      __lowerCamelCase							:			Optional[int]					,      __lowerCamelCase							:			List[str] = None					,      **__lowerCamelCase							:			List[Any]					,      ):


             '''simple docstring'''



             return normalize(__lowerCamelCase					,      mean=__lowerCamelCase					,      std=__lowerCamelCase					,      data_format=__lowerCamelCase					,      **__lowerCamelCase       )





       def 						lowerCAmelCase     (   self							:			Any					,      __lowerCamelCase							:			str					,      __lowerCamelCase							:			str = None					,      __lowerCamelCase							:			List[str] = None					,      __lowerCamelCase							:			Union[str, Any] = None					,      __lowerCamelCase							:			Optional[int] = None					,      __lowerCamelCase							:			int = None					,      __lowerCamelCase							:			Any = None					,      __lowerCamelCase							:			List[Any] = None					,      __lowerCamelCase							:			Any = None					,      __lowerCamelCase							:			int = None					,      __lowerCamelCase							:			Any = None					,      __lowerCamelCase							:			Any = None					,      __lowerCamelCase							:			str = None					,      __lowerCamelCase							:			Dict = ChannelDimension.FIRST					,      **__lowerCamelCase							:			Union[str, Any]					,      ):


             '''simple docstring'''



             lowerCamelCase__		:				Any    =  do_resize if do_resize is not None else self.do_resize
             lowerCamelCase__		:				Optional[int]    =  size if size is not None else self.size
             lowerCamelCase__		:				int    =  get_size_dict(__lowerCamelCase					,      param_name="size"					,      default_to_square=__lowerCamelCase       )
             lowerCamelCase__		:				Optional[int]    =  resample if resample is not None else self.resample
             lowerCamelCase__		:				str    =  do_center_crop if do_center_crop is not None else self.do_center_crop
             lowerCamelCase__		:				Union[str, Any]    =  crop_size if crop_size is not None else self.crop_size
             lowerCamelCase__		:				List[str]    =  get_size_dict(__lowerCamelCase					,      param_name="crop_size"					,      default_to_square=__lowerCamelCase       )
             lowerCamelCase__		:				List[Any]    =  do_rescale if do_rescale is not None else self.do_rescale
             lowerCamelCase__		:				int    =  rescale_factor if rescale_factor is not None else self.rescale_factor
             lowerCamelCase__		:				Dict    =  do_normalize if do_normalize is not None else self.do_normalize
             lowerCamelCase__		:				Union[str, Any]    =  image_mean if image_mean is not None else self.image_mean
             lowerCamelCase__		:				Any    =  image_std if image_std is not None else self.image_std
             lowerCamelCase__		:				Optional[int]    =  do_convert_rgb if do_convert_rgb is not None else self.do_convert_rgb

             lowerCamelCase__		:				Dict    =  make_list_of_images(__lowerCamelCase       )

             if not valid_images(__lowerCamelCase       ):
                   raise ValueError(
                       "Invalid image type. Must be of type PIL.Image.Image, numpy.ndarray, "
                       "torch.Tensor, tf.Tensor or jax.ndarray."       )

             if do_resize and size is None:
                   raise ValueError("Size must be specified if do_resize is True."       )

             if do_center_crop and crop_size is None:
                   raise ValueError("Crop size must be specified if do_center_crop is True."       )

             if do_rescale and rescale_factor is None:
                   raise ValueError("Rescale factor must be specified if do_rescale is True."       )

             if do_normalize and (image_mean is None or image_std is None):
                   raise ValueError("Image mean and std must be specified if do_normalize is True."       )

             # PIL RGBA images are converted to RGB
             if do_convert_rgb:
                   lowerCamelCase__		:				Any    =  [convert_to_rgb(__lowerCamelCase       ) for image in images]

             # All transformations expect numpy arrays.
             lowerCamelCase__		:				List[Any]    =  [to_numpy_array(__lowerCamelCase       ) for image in images]

             if do_resize:
                   lowerCamelCase__		:				Optional[int]    =  [self.resize(image=__lowerCamelCase					,      size=__lowerCamelCase					,      resample=__lowerCamelCase       ) for image in images]

             if do_center_crop:
                   lowerCamelCase__		:				Union[str, Any]    =  [self.center_crop(image=__lowerCamelCase					,      size=__lowerCamelCase       ) for image in images]

             if do_rescale:
                   lowerCamelCase__		:				str    =  [self.rescale(image=__lowerCamelCase					,      scale=__lowerCamelCase       ) for image in images]

             if do_normalize:
                   lowerCamelCase__		:				Optional[int]    =  [self.normalize(image=__lowerCamelCase					,      mean=__lowerCamelCase					,      std=__lowerCamelCase       ) for image in images]

             lowerCamelCase__		:				List[Any]    =  [to_channel_dimension_format(__lowerCamelCase					,      __lowerCamelCase       ) for image in images]

             lowerCamelCase__		:				Dict    =  {"pixel_values": images}
             return BatchFeature(data=__lowerCamelCase					,      tensor_type=__lowerCamelCase       )




import sys
from collections import defaultdict







class        A_   :




	'''simple docstring'''


	def __init__(       self       ):
		lowercase       =    []





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case       ):
		return self.node_position[vertex]





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case       ):
		lowercase       =    pos





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

				lowercase       =    self.get_position(positions[smallest_child]       )
				self.set_position(
				    positions[smallest_child]		,    self.get_position(positions[start]       )       )
				self.set_position(positions[start]		,    snake_case       )

				self.top_to_bottom(snake_case		,    snake_case		,    snake_case		,    snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case		,    snake_case		,    snake_case       ):
		lowercase       =    position[index]

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

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





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case       ):
		lowercase       =    len(snake_case       ) // 2 - 1
		for i in range(snake_case		,    -1		,    -1       ):
			self.top_to_bottom(snake_case		,    snake_case		,    len(snake_case       )		,    snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case       ):
		lowercase       =    positions[0]
		lowercase       =    sys.maxsize
		self.top_to_bottom(snake_case		,    0		,    len(snake_case       )		,    snake_case       )
		return temp






def 							UpperCAmelCase_		(							__SCREAMING_SNAKE_CASE							):
	lowercase       =    Heap()

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

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

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

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

