






"""simple docstring"""





import argparse
import json
import os
import sys
import tempfile
import unittest
from argparse import Namespace
from dataclasses import dataclass, field
from enum import Enum
from pathlib import Path
from typing import List, Literal, Optional

import yaml

from transformers import HfArgumentParser, TrainingArguments
from transformers.hf_argparser import make_choice_type_function, string_to_bool


# Since Python 3.10, we can use the builtin `|` operator for Union types
# See PEP 604: https://peps.python.org/pep-0604
A__					: str=	sys.version_info >= (3, 10)







def   lowerCAmelCase_( SCREAMING_SNAKE_CASE=None ,	SCREAMING_SNAKE_CASE=None					)					->	str:
    """simple docstring"""

    return field(default_factory=lambda: default ,	metadata=SCREAMING_SNAKE_CASE					)
@dataclass
class    __lowerCamelCase    :
   a      :				int
   a      :				float
   a      :				str
   a      :				bool







@dataclass
class    __lowerCamelCase    :
   a      :				int 						=4_2
   a      :				str 						=field(default="""toto"""							,	metadata={"""help""": """help message"""}  )







@dataclass
class    __lowerCamelCase    :
   a      :				bool 						=False
   a      :				bool 						=True
   a      :				Optional[bool] 						=None







class    __lowerCamelCase    (  _a  ):
   a      :				Dict 						="""titi"""
   a      :				Optional[int] 						="""toto"""







class    __lowerCamelCase    (  _a  ):
   a      :				Optional[Any] 						="""titi"""
   a      :				List[Any] 						="""toto"""
   a      :				Tuple 						=4_2







@dataclass
class    __lowerCamelCase    :
   a      :				BasicEnum 						="toto"

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Tuple:
       UpperCamelCase__         =    BasicEnum(self.foo      )







@dataclass
class    __lowerCamelCase    :
   a      :				MixedTypeEnum 						="toto"

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[Any]:
       UpperCamelCase__         =    MixedTypeEnum(self.foo      )







@dataclass
class    __lowerCamelCase    :
   a      :				Optional[int] 						=None
   a      :				Optional[float] 						=field(default=_a							,	metadata={"""help""": """help message"""}  )
   a      :				Optional[str] 						=None
   a      :				Optional[List[str]] 						=list_field(default=[]  )
   a      :				Optional[List[int]] 						=list_field(default=[]  )







@dataclass
class    __lowerCamelCase    :
   a      :				List[int] 						=list_field(default=[]  )
   a      :				List[int] 						=list_field(default=[1, 2, 3]  )
   a      :				List[str] 						=list_field(default=["""Hallo""", """Bonjour""", """Hello"""]  )
   a      :				List[float] 						=list_field(default=[0.1, 0.2, 0.3]  )







@dataclass
class    __lowerCamelCase    :
   a      :				List[int] 						=field()
   a      :				str 						=field()
   a      :				BasicEnum 						=field()

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Dict:
       UpperCamelCase__         =    BasicEnum(self.required_enum      )







@dataclass
class    __lowerCamelCase    :
   a      :				int
   a      :				"BasicEnum" 						=field()
   a      :				"Optional[bool]" 						=None
   a      :				"str" 						=field(default="""toto"""							,	metadata={"""help""": """help message"""}  )
   a      :				"List[str]" 						=list_field(default=["""Hallo""", """Bonjour""", """Hello"""]  )


if is_python_no_less_than_3_10:
  @dataclass
  class    __lowerCamelCase    :
     a      :				bool 						=False
     a      :				bool 						=True
     a      :				bool | None 						=None







  @dataclass
  class    __lowerCamelCase    :
     a      :				int | None 						=None
     a      :				float | None 						=field(default=_a							,	metadata={"""help""": """help message"""}  )
     a      :				str | None 						=None
     a      :				list[str] | None 						=list_field(default=[]  )
     a      :				list[int] | None 						=list_field(default=[]  )





class    __lowerCamelCase    (  unittest.TestCase  ):

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       Union[str, Any]:
       self.assertEqual(len(a._actions      ) ,				len(b._actions      )      )
       for x, y in zip(a._actions ,				b._actions      ):
           UpperCamelCase__         =    {k: v for k, v in vars(snake_case_      ).items() if k != 'container'}
           UpperCamelCase__         =    {k: v for k, v in vars(snake_case_      ).items() if k != 'container'}

           # Choices with mixed type have custom function as "type"
           # So we need to compare results directly for equality
           if xx.get('choices' ,				snake_case_      ) and yy.get('choices' ,				snake_case_      ):
               for expected_choice in yy["choices"] + xx["choices"]:
                   self.assertEqual(xx['type'](snake_case_      ) ,				yy['type'](snake_case_      )      )
               del xx["type"], yy["type"]

           self.assertEqual(snake_case_ ,				snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Dict:
       UpperCamelCase__         =    HfArgumentParser(snake_case_      )

       UpperCamelCase__         =    argparse.ArgumentParser()
       expected.add_argument('--foo' ,				type=snake_case_ ,				required=snake_case_      )
       expected.add_argument('--bar' ,				type=snake_case_ ,				required=snake_case_      )
       expected.add_argument('--baz' ,				type=snake_case_ ,				required=snake_case_      )
       expected.add_argument('--flag' ,				type=snake_case_ ,				default=snake_case_ ,				const=snake_case_ ,				nargs='?'      )
       self.argparsersEqual(snake_case_ ,				snake_case_      )

       UpperCamelCase__         =    ['--foo', '1', '--baz', 'quux', '--bar', '0.5']
       ((UpperCamelCase__)       ,						)         =    parser.parse_args_into_dataclasses(snake_case_ ,				look_for_args_file=snake_case_      )
       self.assertFalse(example.flag      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[int]:
       UpperCamelCase__         =    HfArgumentParser(snake_case_      )

       UpperCamelCase__         =    argparse.ArgumentParser()
       expected.add_argument('--foo' ,				default=42 ,				type=snake_case_      )
       expected.add_argument('--baz' ,				default='toto' ,				type=snake_case_ ,				help='help message'      )
       self.argparsersEqual(snake_case_ ,				snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       UpperCamelCase__         =    argparse.ArgumentParser()
       expected.add_argument('--foo' ,				type=snake_case_ ,				default=snake_case_ ,				const=snake_case_ ,				nargs='?'      )
       expected.add_argument('--baz' ,				type=snake_case_ ,				default=snake_case_ ,				const=snake_case_ ,				nargs='?'      )
       # A boolean no_* argument always has to come after its "default: True" regular counter-part
       # and its default must be set to False
       expected.add_argument('--no_baz' ,				action='store_false' ,				default=snake_case_ ,				dest='baz'      )
       expected.add_argument('--opt' ,				type=snake_case_ ,				default=snake_case_      )

       UpperCamelCase__         =    [WithDefaultBoolExample]
       if is_python_no_less_than_3_10:
           dataclass_types.append(snake_case_      )

       for dataclass_type in dataclass_types:
           UpperCamelCase__         =    HfArgumentParser(snake_case_      )
           self.argparsersEqual(snake_case_ ,				snake_case_      )

           UpperCamelCase__         =    parser.parse_args([]      )
           self.assertEqual(snake_case_ ,				Namespace(foo=snake_case_ ,				baz=snake_case_ ,				opt=snake_case_      )      )

           UpperCamelCase__         =    parser.parse_args(['--foo', '--no_baz']      )
           self.assertEqual(snake_case_ ,				Namespace(foo=snake_case_ ,				baz=snake_case_ ,				opt=snake_case_      )      )

           UpperCamelCase__         =    parser.parse_args(['--foo', '--baz']      )
           self.assertEqual(snake_case_ ,				Namespace(foo=snake_case_ ,				baz=snake_case_ ,				opt=snake_case_      )      )

           UpperCamelCase__         =    parser.parse_args(['--foo', 'True', '--baz', 'True', '--opt', 'True']      )
           self.assertEqual(snake_case_ ,				Namespace(foo=snake_case_ ,				baz=snake_case_ ,				opt=snake_case_      )      )

           UpperCamelCase__         =    parser.parse_args(['--foo', 'False', '--baz', 'False', '--opt', 'False']      )
           self.assertEqual(snake_case_ ,				Namespace(foo=snake_case_ ,				baz=snake_case_ ,				opt=snake_case_      )      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       UpperCamelCase__         =    HfArgumentParser(snake_case_      )

       UpperCamelCase__         =    argparse.ArgumentParser()
       expected.add_argument(
           '--foo' ,				default='toto' ,				choices=['titi', 'toto', 42] ,				type=make_choice_type_function(['titi', 'toto', 42]      ) ,				)
       self.argparsersEqual(snake_case_ ,				snake_case_      )

       UpperCamelCase__         =    parser.parse_args([]      )
       self.assertEqual(args.foo ,				'toto'      )
       UpperCamelCase__         =    parser.parse_args_into_dataclasses([]      )[0]
       self.assertEqual(enum_ex.foo ,				MixedTypeEnum.toto      )

       UpperCamelCase__         =    parser.parse_args(['--foo', 'titi']      )
       self.assertEqual(args.foo ,				'titi'      )
       UpperCamelCase__         =    parser.parse_args_into_dataclasses(['--foo', 'titi']      )[0]
       self.assertEqual(enum_ex.foo ,				MixedTypeEnum.titi      )

       UpperCamelCase__         =    parser.parse_args(['--foo', '42']      )
       self.assertEqual(args.foo ,				42      )
       UpperCamelCase__         =    parser.parse_args_into_dataclasses(['--foo', '42']      )[0]
       self.assertEqual(enum_ex.foo ,				MixedTypeEnum.fourtytwo      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       @dataclass
       class    __lowerCamelCase    :
          a      :				Literal["titi", "toto", 4_2] 						="toto"







       UpperCamelCase__         =    HfArgumentParser(snake_case_      )

       UpperCamelCase__         =    argparse.ArgumentParser()
       expected.add_argument(
           '--foo' ,				default='toto' ,				choices=('titi', 'toto', 42) ,				type=make_choice_type_function(['titi', 'toto', 42]      ) ,				)
       self.argparsersEqual(snake_case_ ,				snake_case_      )

       UpperCamelCase__         =    parser.parse_args([]      )
       self.assertEqual(args.foo ,				'toto'      )

       UpperCamelCase__         =    parser.parse_args(['--foo', 'titi']      )
       self.assertEqual(args.foo ,				'titi'      )

       UpperCamelCase__         =    parser.parse_args(['--foo', '42']      )
       self.assertEqual(args.foo ,				42      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Tuple:
       UpperCamelCase__         =    HfArgumentParser(snake_case_      )

       UpperCamelCase__         =    argparse.ArgumentParser()
       expected.add_argument('--foo_int' ,				nargs='+' ,				default=[] ,				type=snake_case_      )
       expected.add_argument('--bar_int' ,				nargs='+' ,				default=[1, 2, 3] ,				type=snake_case_      )
       expected.add_argument('--foo_str' ,				nargs='+' ,				default=['Hallo', 'Bonjour', 'Hello'] ,				type=snake_case_      )
       expected.add_argument('--foo_float' ,				nargs='+' ,				default=[0.1, 0.2, 0.3] ,				type=snake_case_      )

       self.argparsersEqual(snake_case_ ,				snake_case_      )

       UpperCamelCase__         =    parser.parse_args([]      )
       self.assertEqual(
           snake_case_ ,				Namespace(foo_int=[] ,				bar_int=[1, 2, 3] ,				foo_str=['Hallo', 'Bonjour', 'Hello'] ,				foo_float=[0.1, 0.2, 0.3]      ) ,				)

       UpperCamelCase__         =    parser.parse_args('--foo_int 1 --bar_int 2 3 --foo_str a b c --foo_float 0.1 0.7'.split()      )
       self.assertEqual(snake_case_ ,				Namespace(foo_int=[1] ,				bar_int=[2, 3] ,				foo_str=['a', 'b', 'c'] ,				foo_float=[0.1, 0.7]      )      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Union[str, Any]:
       UpperCamelCase__         =    argparse.ArgumentParser()
       expected.add_argument('--foo' ,				default=snake_case_ ,				type=snake_case_      )
       expected.add_argument('--bar' ,				default=snake_case_ ,				type=snake_case_ ,				help='help message'      )
       expected.add_argument('--baz' ,				default=snake_case_ ,				type=snake_case_      )
       expected.add_argument('--ces' ,				nargs='+' ,				default=[] ,				type=snake_case_      )
       expected.add_argument('--des' ,				nargs='+' ,				default=[] ,				type=snake_case_      )

       UpperCamelCase__         =    [OptionalExample]
       if is_python_no_less_than_3_10:
           dataclass_types.append(snake_case_      )

       for dataclass_type in dataclass_types:
           UpperCamelCase__         =    HfArgumentParser(snake_case_      )

           self.argparsersEqual(snake_case_ ,				snake_case_      )

           UpperCamelCase__         =    parser.parse_args([]      )
           self.assertEqual(snake_case_ ,				Namespace(foo=snake_case_ ,				bar=snake_case_ ,				baz=snake_case_ ,				ces=[] ,				des=[]      )      )

           UpperCamelCase__         =    parser.parse_args('--foo 12 --bar 3.14 --baz 42 --ces a b c --des 1 2 3'.split()      )
           self.assertEqual(snake_case_ ,				Namespace(foo=12 ,				bar=3.14 ,				baz='42' ,				ces=['a', 'b', 'c'] ,				des=[1, 2, 3]      )      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[Any]:
       UpperCamelCase__         =    HfArgumentParser(snake_case_      )

       UpperCamelCase__         =    argparse.ArgumentParser()
       expected.add_argument('--required_list' ,				nargs='+' ,				type=snake_case_ ,				required=snake_case_      )
       expected.add_argument('--required_str' ,				type=snake_case_ ,				required=snake_case_      )
       expected.add_argument(
           '--required_enum' ,				type=make_choice_type_function(['titi', 'toto']      ) ,				choices=['titi', 'toto'] ,				required=snake_case_ ,				)
       self.argparsersEqual(snake_case_ ,				snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       UpperCamelCase__         =    HfArgumentParser(snake_case_      )

       UpperCamelCase__         =    argparse.ArgumentParser()
       expected.add_argument('--foo' ,				type=snake_case_ ,				required=snake_case_      )
       expected.add_argument(
           '--required_enum' ,				type=make_choice_type_function(['titi', 'toto']      ) ,				choices=['titi', 'toto'] ,				required=snake_case_ ,				)
       expected.add_argument('--opt' ,				type=snake_case_ ,				default=snake_case_      )
       expected.add_argument('--baz' ,				default='toto' ,				type=snake_case_ ,				help='help message'      )
       expected.add_argument('--foo_str' ,				nargs='+' ,				default=['Hallo', 'Bonjour', 'Hello'] ,				type=snake_case_      )
       self.argparsersEqual(snake_case_ ,				snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       str:
       UpperCamelCase__         =    HfArgumentParser(snake_case_      )

       UpperCamelCase__         =    {
           'foo': 12,
           'bar': 3.14,
           'baz': '42',
           'flag': True,
       }

       UpperCamelCase__         =    parser.parse_dict(snake_case_      )[0]
       UpperCamelCase__         =    BasicExample(**snake_case_      )
       self.assertEqual(snake_case_ ,				snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Dict:
       UpperCamelCase__         =    HfArgumentParser(snake_case_      )

       UpperCamelCase__         =    {
           'foo': 12,
           'bar': 3.14,
           'baz': '42',
           'flag': True,
           'extra': 42,
       }

       self.assertRaises(snake_case_ ,				parser.parse_dict ,				snake_case_ ,				allow_extra_keys=snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[Any]:
       UpperCamelCase__         =    HfArgumentParser(snake_case_      )

       UpperCamelCase__         =    {
           'foo': 12,
           'bar': 3.14,
           'baz': '42',
           'flag': True,
       }
       with tempfile.TemporaryDirectory() as tmp_dir:
           UpperCamelCase__         =    os.path.join(snake_case_ ,				'temp_json'      )
           os.mkdir(snake_case_      )
           with open(temp_local_path + '.json' ,				'w+'      ) as f:
               json.dump(snake_case_ ,				snake_case_      )
           UpperCamelCase__         =    parser.parse_yaml_file(Path(temp_local_path + '.json'      )      )[0]

       UpperCamelCase__         =    BasicExample(**snake_case_      )
       self.assertEqual(snake_case_ ,				snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[int]:
       UpperCamelCase__         =    HfArgumentParser(snake_case_      )

       UpperCamelCase__         =    {
           'foo': 12,
           'bar': 3.14,
           'baz': '42',
           'flag': True,
       }
       with tempfile.TemporaryDirectory() as tmp_dir:
           UpperCamelCase__         =    os.path.join(snake_case_ ,				'temp_yaml'      )
           os.mkdir(snake_case_      )
           with open(temp_local_path + '.yaml' ,				'w+'      ) as f:
               yaml.dump(snake_case_ ,				snake_case_      )
           UpperCamelCase__         =    parser.parse_yaml_file(Path(temp_local_path + '.yaml'      )      )[0]
       UpperCamelCase__         =    BasicExample(**snake_case_      )
       self.assertEqual(snake_case_ ,				snake_case_      )







   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[int]:
       UpperCamelCase__         =    HfArgumentParser(snake_case_      )
       self.assertIsNotNone(snake_case_      )












"""simple docstring"""





import sys
from collections import defaultdict
class    __lowerCamelCase    :

   def __init__(					self      )		->       Tuple:
       UpperCamelCase__         =    []

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       List[str]:
       return self.node_position[vertex]

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       Optional[int]:
       UpperCamelCase__         =    pos

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

               UpperCamelCase__         =    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_      )		->       Any:
       UpperCamelCase__         =    position[index]

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

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

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       Any:
       UpperCamelCase__         =    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_      )		->       List[Any]:
       UpperCamelCase__         =    positions[0]
       UpperCamelCase__         =    sys.maxsize
       self.top_to_bottom(snake_case_ ,				0 ,				len(snake_case_      ) ,				snake_case_      )
       return temp







def   lowerCAmelCase_( SCREAMING_SNAKE_CASE					)					->	Tuple:
    """simple docstring"""

    UpperCamelCase__         =    Heap()

    UpperCamelCase__         =    [0] * len(SCREAMING_SNAKE_CASE					)
    UpperCamelCase__         =    [-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
    UpperCamelCase__         =    []  # Heap of Distance of vertices from their neighboring vertex
    UpperCamelCase__         =    []

    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					)

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

    for _ in range(1 ,	len(SCREAMING_SNAKE_CASE					)					):
        UpperCamelCase__         =    heap.delete_minimum(SCREAMING_SNAKE_CASE ,	SCREAMING_SNAKE_CASE					)
        if visited[vertex] == 0:
            tree_edges.append((nbr_tv[vertex], vertex)					)
            UpperCamelCase__         =    1
            for neighbor, distance in adjacency_list[vertex]:
                if (
                    visited[neighbor] == 0
                    and distance < distance_tv[heap.get_position(SCREAMING_SNAKE_CASE					)]
                ):
                    UpperCamelCase__         =    distance
                    heap.bottom_to_top(
                        SCREAMING_SNAKE_CASE ,	heap.get_position(SCREAMING_SNAKE_CASE					) ,	SCREAMING_SNAKE_CASE ,	SCREAMING_SNAKE_CASE					)
                    UpperCamelCase__         =    vertex
    return tree_edges


if __name__ == "__main__":  # pragma: no cover
  # < --------- Prims Algorithm --------- >
  A__					: Dict=	int(input("""Enter number of edges: """).strip())
  A__					: Dict=	defaultdict(list)
  for _ in range(edges_number):
    A__					: Dict=	[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))




