



import sys
from collections import defaultdict



class  __lowerCAmelCase     :




 def __init__(						self				):



    '''simple docstring'''
    __lowerCamelCase													=    []




 def        lowerCamelCase      (						self	,				__UpperCAmelCase				):



    '''simple docstring'''
    return self.node_position[vertex]




 def        lowerCamelCase      (						self	,				__UpperCAmelCase	,				__UpperCAmelCase				):



    '''simple docstring'''
    __lowerCamelCase													=    pos




 def        lowerCamelCase      (						self	,				__UpperCAmelCase	,				__UpperCAmelCase	,				__UpperCAmelCase	,				__UpperCAmelCase				):



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

          __lowerCamelCase													=    self.get_position(positions[smallest_child]				)
          self.set_position(
              positions[smallest_child]	,				self.get_position(positions[start]				)				)
          self.set_position(positions[start]	,				__UpperCAmelCase				)

          self.top_to_bottom(__UpperCAmelCase	,				__UpperCAmelCase	,				__UpperCAmelCase	,				__UpperCAmelCase				)




 def        lowerCamelCase      (						self	,				__UpperCAmelCase	,				__UpperCAmelCase	,				__UpperCAmelCase	,				__UpperCAmelCase				):



    '''simple docstring'''
    __lowerCamelCase													=    position[index]

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

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




 def        lowerCamelCase      (						self	,				__UpperCAmelCase	,				__UpperCAmelCase				):



    '''simple docstring'''
    __lowerCamelCase													=    len(__UpperCAmelCase				) // 2 - 1
    for i in range(__UpperCAmelCase	,				-1	,				-1				):
       self.top_to_bottom(__UpperCAmelCase	,				__UpperCAmelCase	,				len(__UpperCAmelCase				)	,				__UpperCAmelCase				)




 def        lowerCamelCase      (						self	,				__UpperCAmelCase	,				__UpperCAmelCase				):



    '''simple docstring'''
    __lowerCamelCase													=    positions[0]
    __lowerCamelCase													=    sys.maxsize
    self.top_to_bottom(__UpperCAmelCase	,				0	,				len(__UpperCAmelCase				)	,				__UpperCAmelCase				)
    return temp





def 		a__			(		_UpperCamelCase			: str							):
   __lowerCamelCase													=    Heap()

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

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

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

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











import unittest

from transformers import MODEL_FOR_DOCUMENT_QUESTION_ANSWERING_MAPPING, AutoTokenizer, is_vision_available
from transformers.pipelines import pipeline
from transformers.pipelines.document_question_answering import apply_tesseract
from transformers.testing_utils import (
    is_pipeline_test,
    nested_simplify,
    require_detectrona,
    require_pytesseract,
    require_tf,
    require_torch,
    require_vision,
    slow,
)

from .test_pipelines_common import ANY


if is_vision_available():
  from PIL import Image

  from transformers.image_utils import load_image
else:



  class  __lowerCAmelCase     :




   @staticmethod
   def        lowerCamelCase      (						*__UpperCAmelCase	,				**__UpperCAmelCase				):



      '''simple docstring'''
      pass





  def 		a__			(		_UpperCamelCase			: List[str]							):
     return None


# This is a pinned image from a specific revision of a document question answering space, hosted by HuggingFace,
# so we can expect it to be available.
a_			=					(
    """https://huggingface.co/spaces/impira/docquery/resolve/2f6c96314dc84dfda62d40de9da55f2f5165d403/invoice.png"""
)



@is_pipeline_test
@require_torch
@require_vision
class  __lowerCAmelCase     (	unittest.TestCase   ):
 lowerCAmelCase__       					=  MODEL_FOR_DOCUMENT_QUESTION_ANSWERING_MAPPING




 @require_pytesseract
 @require_vision
 def        lowerCamelCase      (						self	,				__UpperCAmelCase	,				__UpperCAmelCase	,				__UpperCAmelCase				):



    '''simple docstring'''
    __lowerCamelCase													=    pipeline(
        '''document-question-answering'''	,				model=__UpperCAmelCase	,				tokenizer=__UpperCAmelCase	,				image_processor=__UpperCAmelCase				)

    __lowerCamelCase													=    INVOICE_URL
    __lowerCamelCase													=    list(zip(*apply_tesseract(load_image(__UpperCAmelCase				)	,				__UpperCAmelCase	,				''''''				)				)				)
    __lowerCamelCase													=    '''What is the placebo?'''
    __lowerCamelCase													=    [
        {
            '''image''': load_image(__UpperCAmelCase				),
            '''question''': question,
        },
        {
            '''image''': image,
            '''question''': question,
        },
        {
            '''image''': image,
            '''question''': question,
            '''word_boxes''': word_boxes,
        },
    ]
    return dqa_pipeline, examples




 def        lowerCamelCase      (						self	,				__UpperCAmelCase	,				__UpperCAmelCase				):



    '''simple docstring'''
    __lowerCamelCase													=    dqa_pipeline(__UpperCAmelCase	,				top_k=2				)
    self.assertEqual(
        __UpperCAmelCase	,				[
            [
                {'''score''': ANY(__UpperCAmelCase				), '''answer''': ANY(__UpperCAmelCase				), '''start''': ANY(__UpperCAmelCase				), '''end''': ANY(__UpperCAmelCase				)},
                {'''score''': ANY(__UpperCAmelCase				), '''answer''': ANY(__UpperCAmelCase				), '''start''': ANY(__UpperCAmelCase				), '''end''': ANY(__UpperCAmelCase				)},
            ]
        ]
        * 3	,				)




 @require_torch
 @require_detectrona
 @require_pytesseract
 def        lowerCamelCase      (						self				):



    '''simple docstring'''
    __lowerCamelCase													=    pipeline('''document-question-answering'''	,				model='''hf-internal-testing/tiny-random-layoutlmv2'''				)
    __lowerCamelCase													=    INVOICE_URL
    __lowerCamelCase													=    '''How many cats are there?'''

    __lowerCamelCase													=    [
        {'''score''': 0.0_001, '''answer''': '''oy 2312/2019''', '''start''': 38, '''end''': 39},
        {'''score''': 0.0_001, '''answer''': '''oy 2312/2019 DUE''', '''start''': 38, '''end''': 40},
    ]
    __lowerCamelCase													=    dqa_pipeline(image=__UpperCAmelCase	,				question=__UpperCAmelCase	,				top_k=2				)
    self.assertEqual(nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				__UpperCAmelCase				)

    __lowerCamelCase													=    dqa_pipeline({'''image''': image, '''question''': question}	,				top_k=2				)
    self.assertEqual(nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				__UpperCAmelCase				)

    # This image does not detect ANY text in it, meaning layoutlmv2 should fail.
    # Empty answer probably
    __lowerCamelCase													=    '''./tests/fixtures/tests_samples/COCO/000000039769.png'''
    __lowerCamelCase													=    dqa_pipeline(image=__UpperCAmelCase	,				question=__UpperCAmelCase	,				top_k=2				)
    self.assertEqual(__UpperCAmelCase	,				[]				)

    # We can optionnally pass directly the words and bounding boxes
    __lowerCamelCase													=    '''./tests/fixtures/tests_samples/COCO/000000039769.png'''
    __lowerCamelCase													=    []
    __lowerCamelCase													=    []
    __lowerCamelCase													=    dqa_pipeline(image=__UpperCAmelCase	,				question=__UpperCAmelCase	,				words=__UpperCAmelCase	,				boxes=__UpperCAmelCase	,				top_k=2				)
    self.assertEqual(__UpperCAmelCase	,				[]				)




 @slow
 @require_torch
 @require_detectrona
 @require_pytesseract
 def        lowerCamelCase      (						self				):



    '''simple docstring'''
    __lowerCamelCase													=    pipeline(
        '''document-question-answering'''	,				model='''tiennvcs/layoutlmv2-base-uncased-finetuned-docvqa'''	,				revision='''9977165'''	,				)
    __lowerCamelCase													=    INVOICE_URL
    __lowerCamelCase													=    '''What is the invoice number?'''

    __lowerCamelCase													=    dqa_pipeline(image=__UpperCAmelCase	,				question=__UpperCAmelCase	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            {'''score''': 0.9_944, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
            {'''score''': 0.0_009, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
        ]	,				)

    __lowerCamelCase													=    dqa_pipeline({'''image''': image, '''question''': question}	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            {'''score''': 0.9_944, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
            {'''score''': 0.0_009, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
        ]	,				)

    __lowerCamelCase													=    dqa_pipeline(
        [{'''image''': image, '''question''': question}, {'''image''': image, '''question''': question}]	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            [
                {'''score''': 0.9_944, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
                {'''score''': 0.0_009, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
            ],
        ]
        * 2	,				)




 @slow
 @require_torch
 @require_detectrona
 @require_pytesseract
 def        lowerCamelCase      (						self				):



    '''simple docstring'''
    __lowerCamelCase													=    pipeline(
        '''document-question-answering'''	,				model='''tiennvcs/layoutlmv2-base-uncased-finetuned-docvqa'''	,				revision='''9977165'''	,				max_seq_len=50	,				)
    __lowerCamelCase													=    INVOICE_URL
    __lowerCamelCase													=    '''What is the invoice number?'''

    __lowerCamelCase													=    dqa_pipeline(image=__UpperCAmelCase	,				question=__UpperCAmelCase	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            {'''score''': 0.9_974, '''answer''': '''1110212019''', '''start''': 23, '''end''': 23},
            {'''score''': 0.9_948, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
        ]	,				)

    __lowerCamelCase													=    dqa_pipeline({'''image''': image, '''question''': question}	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            {'''score''': 0.9_974, '''answer''': '''1110212019''', '''start''': 23, '''end''': 23},
            {'''score''': 0.9_948, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
        ]	,				)

    __lowerCamelCase													=    dqa_pipeline(
        [{'''image''': image, '''question''': question}, {'''image''': image, '''question''': question}]	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            [
                {'''score''': 0.9_974, '''answer''': '''1110212019''', '''start''': 23, '''end''': 23},
                {'''score''': 0.9_948, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
            ]
        ]
        * 2	,				)




 @slow
 @require_torch
 @require_pytesseract
 @require_vision
 def        lowerCamelCase      (						self				):



    '''simple docstring'''
    __lowerCamelCase													=    AutoTokenizer.from_pretrained(
        '''impira/layoutlm-document-qa'''	,				revision='''3dc6de3'''	,				add_prefix_space=__UpperCAmelCase				)
    __lowerCamelCase													=    pipeline(
        '''document-question-answering'''	,				model='''impira/layoutlm-document-qa'''	,				tokenizer=__UpperCAmelCase	,				revision='''3dc6de3'''	,				)
    __lowerCamelCase													=    INVOICE_URL
    __lowerCamelCase													=    '''What is the invoice number?'''

    __lowerCamelCase													=    dqa_pipeline(image=__UpperCAmelCase	,				question=__UpperCAmelCase	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            {'''score''': 0.4_251, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
            {'''score''': 0.0_819, '''answer''': '''1110212019''', '''start''': 23, '''end''': 23},
        ]	,				)

    __lowerCamelCase													=    dqa_pipeline({'''image''': image, '''question''': question}	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            {'''score''': 0.4_251, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
            {'''score''': 0.0_819, '''answer''': '''1110212019''', '''start''': 23, '''end''': 23},
        ]	,				)

    __lowerCamelCase													=    dqa_pipeline(
        [{'''image''': image, '''question''': question}, {'''image''': image, '''question''': question}]	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            [
                {'''score''': 0.4_251, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
                {'''score''': 0.0_819, '''answer''': '''1110212019''', '''start''': 23, '''end''': 23},
            ]
        ]
        * 2	,				)

    __lowerCamelCase													=    list(zip(*apply_tesseract(load_image(__UpperCAmelCase				)	,				__UpperCAmelCase	,				''''''				)				)				)

    # This model should also work if `image` is set to None
    __lowerCamelCase													=    dqa_pipeline({'''image''': None, '''word_boxes''': word_boxes, '''question''': question}	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            {'''score''': 0.4_251, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
            {'''score''': 0.0_819, '''answer''': '''1110212019''', '''start''': 23, '''end''': 23},
        ]	,				)




 @slow
 @require_torch
 @require_pytesseract
 @require_vision
 def        lowerCamelCase      (						self				):



    '''simple docstring'''
    __lowerCamelCase													=    AutoTokenizer.from_pretrained(
        '''impira/layoutlm-document-qa'''	,				revision='''3dc6de3'''	,				add_prefix_space=__UpperCAmelCase				)
    __lowerCamelCase													=    pipeline(
        '''document-question-answering'''	,				model='''impira/layoutlm-document-qa'''	,				tokenizer=__UpperCAmelCase	,				revision='''3dc6de3'''	,				max_seq_len=50	,				)
    __lowerCamelCase													=    INVOICE_URL
    __lowerCamelCase													=    '''What is the invoice number?'''

    __lowerCamelCase													=    dqa_pipeline(image=__UpperCAmelCase	,				question=__UpperCAmelCase	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            {'''score''': 0.9_999, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
            {'''score''': 0.9_998, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
        ]	,				)

    __lowerCamelCase													=    dqa_pipeline(
        [{'''image''': image, '''question''': question}, {'''image''': image, '''question''': question}]	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            [
                {'''score''': 0.9_999, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
                {'''score''': 0.9_998, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
            ]
        ]
        * 2	,				)

    __lowerCamelCase													=    list(zip(*apply_tesseract(load_image(__UpperCAmelCase				)	,				__UpperCAmelCase	,				''''''				)				)				)

    # This model should also work if `image` is set to None
    __lowerCamelCase													=    dqa_pipeline({'''image''': None, '''word_boxes''': word_boxes, '''question''': question}	,				top_k=2				)
    self.assertEqual(
        nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[
            {'''score''': 0.9_999, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
            {'''score''': 0.9_998, '''answer''': '''us-001''', '''start''': 16, '''end''': 16},
        ]	,				)




 @slow
 @require_torch
 def        lowerCamelCase      (						self				):



    '''simple docstring'''
    __lowerCamelCase													=    pipeline(
        '''document-question-answering'''	,				model='''naver-clova-ix/donut-base-finetuned-docvqa'''	,				tokenizer=AutoTokenizer.from_pretrained('''naver-clova-ix/donut-base-finetuned-docvqa'''				)	,				feature_extractor='''naver-clova-ix/donut-base-finetuned-docvqa'''	,				)

    __lowerCamelCase													=    INVOICE_URL
    __lowerCamelCase													=    '''What is the invoice number?'''
    __lowerCamelCase													=    dqa_pipeline(image=__UpperCAmelCase	,				question=__UpperCAmelCase	,				top_k=2				)
    self.assertEqual(nested_simplify(__UpperCAmelCase	,				decimals=4				)	,				[{'''answer''': '''us-001'''}]				)




 @require_tf
 @unittest.skip('''Document question answering not implemented in TF'''				)
 def        lowerCamelCase      (						self				):



    '''simple docstring'''
    pass






