
from typing import Dict, Iterable, Optional, Union

import numpy as np

from ...image_processing_utils import BaseImageProcessor, BatchFeature, get_size_dict
from ...image_transforms import normalize, rescale, resize, to_channel_dimension_format, to_pil_image
from ...image_utils import (
    IMAGENET_STANDARD_MEAN,
    IMAGENET_STANDARD_STD,
    ChannelDimension,
    ImageInput,
    PILImageResampling,
    make_list_of_images,
    to_numpy_array,
    valid_images,
)
from ...utils import TensorType, is_pytesseract_available, is_vision_available, logging, requires_backends


if is_vision_available():
	import PIL

# soft dependency
if is_pytesseract_available():
	import pytesseract

UpperCAmelCase	      = logging.get_logger(__name__)






def 							UpperCAmelCase_		(							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							):
	return [
	    int(1000 * (box[0] / width)							),
	    int(1000 * (box[1] / height)							),
	    int(1000 * (box[2] / width)							),
	    int(1000 * (box[3] / height)							),
	]






def 							UpperCAmelCase_		(							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							):
	lowercase       =    to_pil_image(__SCREAMING_SNAKE_CASE							)
	lowercase  ,					lowercase       =    pil_image.size
	lowercase       =    pytesseract.image_to_data(__SCREAMING_SNAKE_CASE ,							lang=__SCREAMING_SNAKE_CASE ,							output_type='dict' ,							config=__SCREAMING_SNAKE_CASE							)
	lowercase  ,					lowercase  ,					lowercase  ,					lowercase  ,					lowercase       =    data['text'], data['left'], data['top'], data['width'], data['height']

	# filter empty words and corresponding coordinates
	lowercase       =    [idx for idx, word in enumerate(__SCREAMING_SNAKE_CASE							) if not word.strip()]
	lowercase       =    [word for idx, word in enumerate(__SCREAMING_SNAKE_CASE							) if idx not in irrelevant_indices]
	lowercase       =    [coord for idx, coord in enumerate(__SCREAMING_SNAKE_CASE							) if idx not in irrelevant_indices]
	lowercase       =    [coord for idx, coord in enumerate(__SCREAMING_SNAKE_CASE							) if idx not in irrelevant_indices]
	lowercase       =    [coord for idx, coord in enumerate(__SCREAMING_SNAKE_CASE							) if idx not in irrelevant_indices]
	lowercase       =    [coord for idx, coord in enumerate(__SCREAMING_SNAKE_CASE							) if idx not in irrelevant_indices]

	# turn coordinates into (left, top, left+width, top+height) format
	lowercase       =    []
	for x, y, w, h in zip(__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							):
		lowercase       =    [x, y, x + w, y + h]
		actual_boxes.append(__SCREAMING_SNAKE_CASE							)

	# finally, normalize the bounding boxes
	lowercase       =    []
	for box in actual_boxes:
		normalized_boxes.append(normalize_box(__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE ,							__SCREAMING_SNAKE_CASE							)							)

	assert len(__SCREAMING_SNAKE_CASE							) == len(__SCREAMING_SNAKE_CASE							), "Not as many words as there are bounding boxes"

	return words, normalized_boxes







class        A_   (			__lowerCamelCase   ):




	'''simple docstring'''


	_UpperCamelCase     :     Dict							 =       ["""pixel_values"""]





	def __init__(       self		,    snake_case = True		,    snake_case = None		,    snake_case = PILImageResampling.BILINEAR		,    snake_case = True		,    snake_case = 1 / 255		,    snake_case = True		,    snake_case = None		,    snake_case = None		,    snake_case = True		,    snake_case = None		,    snake_case = ""		,    **snake_case		,    ):
		super().__init__(**snake_case       )
		lowercase       =    size if size is not None else {'height': 224, 'width': 224}
		lowercase       =    get_size_dict(snake_case       )

		lowercase       =    do_resize
		lowercase       =    size
		lowercase       =    resample
		lowercase       =    do_rescale
		lowercase       =    rescale_value
		lowercase       =    do_normalize
		lowercase       =    image_mean if image_mean is not None else IMAGENET_STANDARD_MEAN
		lowercase       =    image_std if image_std is not None else IMAGENET_STANDARD_STD
		lowercase       =    apply_ocr
		lowercase       =    ocr_lang
		lowercase       =    tesseract_config





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case		,    snake_case = PILImageResampling.BILINEAR		,    snake_case = None		,    **snake_case		,    ):
		lowercase       =    get_size_dict(snake_case       )
		if "height" not in size or "width" not in size:
			raise ValueError(F'''The size dictionary must contain the keys \'height\' and \'width\'. Got {size.keys()}'''       )
		lowercase       =    (size['height'], size['width'])
		return resize(snake_case		,    size=snake_case		,    resample=snake_case		,    data_format=snake_case		,    **snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case		,    snake_case = None		,    **snake_case		,    ):
		return rescale(snake_case		,    scale=snake_case		,    data_format=snake_case		,    **snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case		,    snake_case		,    snake_case = None		,    **snake_case		,    ):
		return normalize(snake_case		,    mean=snake_case		,    std=snake_case		,    data_format=snake_case		,    **snake_case       )





	def 	SCREAMING_SNAKE_CASE__						(       self		,    snake_case		,    snake_case = None		,    snake_case = None		,    snake_case=None		,    snake_case = None		,    snake_case = None		,    snake_case = None		,    snake_case = None		,    snake_case = None		,    snake_case = None		,    snake_case = None		,    snake_case = None		,    snake_case = None		,    snake_case = ChannelDimension.FIRST		,    **snake_case		,    ):
		lowercase       =    do_resize if do_resize is not None else self.do_resize
		lowercase       =    size if size is not None else self.size
		lowercase       =    get_size_dict(snake_case       )
		lowercase       =    resample if resample is not None else self.resample
		lowercase       =    do_rescale if do_rescale is not None else self.do_rescale
		lowercase       =    rescale_factor if rescale_factor is not None else self.rescale_factor
		lowercase       =    do_normalize if do_normalize is not None else self.do_normalize
		lowercase       =    image_mean if image_mean is not None else self.image_mean
		lowercase       =    image_std if image_std is not None else self.image_std
		lowercase       =    apply_ocr if apply_ocr is not None else self.apply_ocr
		lowercase       =    ocr_lang if ocr_lang is not None else self.ocr_lang
		lowercase       =    tesseract_config if tesseract_config is not None else self.tesseract_config

		lowercase       =    make_list_of_images(snake_case       )

		if not valid_images(snake_case       ):
			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_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('If do_normalize is True, image_mean and image_std must be specified.'       )

		# All transformations expect numpy arrays.
		lowercase       =    [to_numpy_array(snake_case       ) for image in images]

		# Tesseract OCR to get words + normalized bounding boxes
		if apply_ocr:
			requires_backends(self		,    'pytesseract'       )
			lowercase       =    []
			lowercase       =    []
			for image in images:
				lowercase  ,					lowercase       =    apply_tesseract(snake_case		,    snake_case		,    snake_case       )
				words_batch.append(snake_case       )
				boxes_batch.append(snake_case       )

		if do_resize:
			lowercase       =    [self.resize(image=snake_case		,    size=snake_case		,    resample=snake_case       ) for image in images]

		if do_rescale:
			lowercase       =    [self.rescale(image=snake_case		,    scale=snake_case       ) for image in images]

		if do_normalize:
			lowercase       =    [self.normalize(image=snake_case		,    mean=snake_case		,    std=snake_case       ) for image in images]

		lowercase       =    [to_channel_dimension_format(snake_case		,    snake_case       ) for image in images]

		lowercase       =    BatchFeature(data={'pixel_values': images}		,    tensor_type=snake_case       )

		if apply_ocr:
			lowercase       =    words_batch
			lowercase       =    boxes_batch
		return data



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))

