
"""simple docstring"""


import json
import os
import shutil
import tempfile
import unittest

import numpy as np
import pytest

from transformers import CLIPTokenizer, CLIPTokenizerFast
from transformers.models.clip.tokenization_clip import VOCAB_FILES_NAMES
from transformers.testing_utils import require_vision
from transformers.utils import IMAGE_PROCESSOR_NAME, is_vision_available


if is_vision_available():
		from PIL import Image

		from transformers import CLIPSegProcessor, ViTImageProcessor







@require_vision
class 				lowerCAmelCase_				(      unittest.TestCase    ):



						'''simple docstring'''


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   Optional[Any]:
								A						   =   tempfile.mkdtemp()

								# fmt: off
								A						   =   ['l', 'o', 'w', 'e', 'r', 's', 't', 'i', 'd', 'n', 'lo', 'l</w>', 'w</w>', 'r</w>', 't</w>', 'low</w>', 'er</w>', 'lowest</w>', 'newer</w>', 'wider', '<unk>', '<|startoftext|>', '<|endoftext|>']
								# fmt: on
								A						   =   dict(zip(A_  ,range(len(A_      )      )      )      )
								A						   =   ['#version: 0.2', 'l o', 'lo w</w>', 'e r</w>', '']
								A						   =   {'unk_token': '<unk>'}

								A						   =   os.path.join(self.tmpdirname  ,VOCAB_FILES_NAMES['vocab_file']      )
								A						   =   os.path.join(self.tmpdirname  ,VOCAB_FILES_NAMES['merges_file']      )
								with open(self.vocab_file  ,'w'  ,encoding='utf-8'      ) as fp:
										fp.write(json.dumps(A_      ) + '\n'      )
								with open(self.merges_file  ,'w'  ,encoding='utf-8'      ) as fp:
										fp.write('\n'.join(A_      )      )

								A						   =   {
								    'do_resize': True,
								    'size': 20,
								    'do_center_crop': True,
								    'crop_size': 18,
								    'do_normalize': True,
								    'image_mean': [0.48_14_54_66, 0.4_57_82_75, 0.40_82_10_73],
								    'image_std': [0.26_86_29_54, 0.26_13_02_58, 0.27_57_77_11],
								}
								A						   =   os.path.join(self.tmpdirname  ,A_      )
								with open(self.image_processor_file  ,'w'  ,encoding='utf-8'      ) as fp:
										json.dump(A_  ,A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,**A_     :      List[str]      )     ->   List[Any]:
								return CLIPTokenizer.from_pretrained(self.tmpdirname  ,**A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]  ,**A_     :      int      )     ->   Union[str, Any]:
								return CLIPTokenizerFast.from_pretrained(self.tmpdirname  ,**A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]  ,**A_     :      Optional[int]      )     ->   List[Any]:
								return ViTImageProcessor.from_pretrained(self.tmpdirname  ,**A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   Tuple:
								shutil.rmtree(self.tmpdirname      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   Tuple:
								A						   =   [np.random.randint(255  ,size=(3, 30, 400)  ,dtype=np.uinta      )]

								A						   =   [Image.fromarray(np.moveaxis(A_  ,0  ,-1      )      ) for x in image_inputs]

								return image_inputs


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   Any:
								A						   =   self.get_tokenizer()
								A						   =   self.get_rust_tokenizer()
								A						   =   self.get_image_processor()

								A						   =   CLIPSegProcessor(tokenizer=A_  ,image_processor=A_      )
								processor_slow.save_pretrained(self.tmpdirname      )
								A						   =   CLIPSegProcessor.from_pretrained(self.tmpdirname  ,use_fast=A_      )

								A						   =   CLIPSegProcessor(tokenizer=A_  ,image_processor=A_      )
								processor_fast.save_pretrained(self.tmpdirname      )
								A						   =   CLIPSegProcessor.from_pretrained(self.tmpdirname      )

								self.assertEqual(processor_slow.tokenizer.get_vocab()  ,tokenizer_slow.get_vocab()      )
								self.assertEqual(processor_fast.tokenizer.get_vocab()  ,tokenizer_fast.get_vocab()      )
								self.assertEqual(tokenizer_slow.get_vocab()  ,tokenizer_fast.get_vocab()      )
								self.assertIsInstance(processor_slow.tokenizer  ,A_      )
								self.assertIsInstance(processor_fast.tokenizer  ,A_      )

								self.assertEqual(processor_slow.image_processor.to_json_string()  ,image_processor.to_json_string()      )
								self.assertEqual(processor_fast.image_processor.to_json_string()  ,image_processor.to_json_string()      )
								self.assertIsInstance(processor_slow.image_processor  ,A_      )
								self.assertIsInstance(processor_fast.image_processor  ,A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[int]:
								A						   =   CLIPSegProcessor(tokenizer=self.get_tokenizer()  ,image_processor=self.get_image_processor()      )
								processor.save_pretrained(self.tmpdirname      )

								A						   =   self.get_tokenizer(bos_token='(BOS)'  ,eos_token='(EOS)'      )
								A						   =   self.get_image_processor(do_normalize=A_  ,padding_value=1.0      )

								A						   =   CLIPSegProcessor.from_pretrained(
								    self.tmpdirname  ,bos_token='(BOS)'  ,eos_token='(EOS)'  ,do_normalize=A_  ,padding_value=1.0      )

								self.assertEqual(processor.tokenizer.get_vocab()  ,tokenizer_add_kwargs.get_vocab()      )
								self.assertIsInstance(processor.tokenizer  ,A_      )

								self.assertEqual(processor.image_processor.to_json_string()  ,image_processor_add_kwargs.to_json_string()      )
								self.assertIsInstance(processor.image_processor  ,A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]      )     ->   Dict:
								A						   =   self.get_image_processor()
								A						   =   self.get_tokenizer()

								A						   =   CLIPSegProcessor(tokenizer=A_  ,image_processor=A_      )

								A						   =   self.prepare_image_inputs()

								A						   =   image_processor(A_  ,return_tensors='np'      )
								A						   =   processor(images=A_  ,return_tensors='np'      )

								for key in input_feat_extract.keys():
										self.assertAlmostEqual(input_feat_extract[key].sum()  ,input_processor[key].sum()  ,delta=1e-2      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   Union[str, Any]:
								A						   =   self.get_image_processor()
								A						   =   self.get_tokenizer()

								A						   =   CLIPSegProcessor(tokenizer=A_  ,image_processor=A_      )

								A						   =   'lower newer'

								A						   =   processor(text=A_      )

								A						   =   tokenizer(A_      )

								for key in encoded_tok.keys():
										self.assertListEqual(encoded_tok[key]  ,encoded_processor[key]      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str      )     ->   Optional[int]:
								A						   =   self.get_image_processor()
								A						   =   self.get_tokenizer()

								A						   =   CLIPSegProcessor(tokenizer=A_  ,image_processor=A_      )

								A						   =   'lower newer'
								A						   =   self.prepare_image_inputs()

								A						   =   processor(text=A_  ,images=A_      )

								self.assertListEqual(list(inputs.keys()      )  ,['input_ids', 'attention_mask', 'pixel_values']      )

								# test if it raises when no input is passed
								with pytest.raises(A_      ):
										processor()


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]      )     ->   Dict:
								A						   =   self.get_image_processor()
								A						   =   self.get_tokenizer()

								A						   =   CLIPSegProcessor(tokenizer=A_  ,image_processor=A_      )

								A						   =   self.prepare_image_inputs()
								A						   =   self.prepare_image_inputs()

								A						   =   processor(images=A_  ,visual_prompt=A_      )

								self.assertListEqual(list(inputs.keys()      )  ,['pixel_values', 'conditional_pixel_values']      )

								# test if it raises when no input is passed
								with pytest.raises(A_      ):
										processor()




						def 						_SCREAMING_SNAKE_CASE      ( self     :      str      )     ->   List[Any]:
								A						   =   self.get_image_processor()
								A						   =   self.get_tokenizer()

								A						   =   CLIPSegProcessor(tokenizer=A_  ,image_processor=A_      )

								A						   =   [[1, 4, 5, 8, 1, 0, 8], [3, 4, 3, 1, 1, 8, 9]]

								A						   =   processor.batch_decode(A_      )
								A						   =   tokenizer.batch_decode(A_      )

								self.assertListEqual(A_  ,A_      )

"""simple docstring"""


import sys
from collections import defaultdict







class 				lowerCAmelCase_				:



						'''simple docstring'''


						def __init__( self     :      Optional[Any]      )     ->   int:
							A						   =   []


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      int      )     ->   Optional[int]:
							return self.node_position[vertex]


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      List[Any]  ,A_     :      Any      )     ->   List[Any]:
							A						   =   pos


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      str  ,A_     :      str  ,A_     :      Dict  ,A_     :      List[str]      )     ->   str:
							if start > size // 2 - 1:
								return
							else:
								if 2 * start + 2 >= size:
									A						   =   2 * start + 1
								else:
									if heap[2 * start + 1] < heap[2 * start + 2]:
										A						   =   2 * start + 1
									else:
										A						   =   2 * start + 2
								if heap[smallest_child] < heap[start]:
									A   ,      A						   =   heap[smallest_child], positions[smallest_child]
									A   ,      A						   =   (
									    heap[start],
									    positions[start],
									)
									A   ,      A						   =   temp, tempa

									A						   =   self.get_position(positions[smallest_child]      )
									self.set_position(
									    positions[smallest_child]  ,self.get_position(positions[start]      )      )
									self.set_position(positions[start]  ,A_      )

									self.top_to_bottom(A_  ,A_  ,A_  ,A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str  ,A_     :      Optional[int]  ,A_     :      Dict  ,A_     :      str  ,A_     :      Union[str, Any]      )     ->   Dict:
							A						   =   position[index]

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

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Tuple  ,A_     :      Dict      )     ->   Union[str, Any]:
							A						   =   len(A_      ) // 2 - 1
							for i in range(A_  ,-1  ,-1      ):
								self.top_to_bottom(A_  ,A_  ,len(A_      )  ,A_      )




						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Optional[int]  ,A_     :      Dict      )     ->   Union[str, Any]:
							A						   =   positions[0]
							A						   =   sys.maxsize
							self.top_to_bottom(A_  ,0  ,len(A_      )  ,A_      )
							return temp






def       _snake_case				(		snake_case__   :     Dict     ):
	A						   =   Heap()

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

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

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

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