
'''simple docstring'''



from . import __version__

# Backward compatibility imports, to make sure all those objects can be found in file_utils
from .utils import (
    CLOUDFRONT_DISTRIB_PREFIX,
    CONFIG_NAME,
    DISABLE_TELEMETRY,
    DUMMY_INPUTS,
    DUMMY_MASK,
    ENV_VARS_TRUE_AND_AUTO_VALUES,
    ENV_VARS_TRUE_VALUES,
    FEATURE_EXTRACTOR_NAME,
    FLAX_WEIGHTS_NAME,
    HF_MODULES_CACHE,
    HUGGINGFACE_CO_PREFIX,
    HUGGINGFACE_CO_RESOLVE_ENDPOINT,
    MODEL_CARD_NAME,
    MULTIPLE_CHOICE_DUMMY_INPUTS,
    PYTORCH_PRETRAINED_BERT_CACHE,
    PYTORCH_TRANSFORMERS_CACHE,
    S3_BUCKET_PREFIX,
    SENTENCEPIECE_UNDERLINE,
    SPIECE_UNDERLINE,
    TF2_WEIGHTS_NAME,
    TF_WEIGHTS_NAME,
    TORCH_FX_REQUIRED_VERSION,
    TRANSFORMERS_CACHE,
    TRANSFORMERS_DYNAMIC_MODULE_NAME,
    USE_JAX,
    USE_TF,
    USE_TORCH,
    WEIGHTS_INDEX_NAME,
    WEIGHTS_NAME,
    ContextManagers,
    DummyObject,
    EntryNotFoundError,
    ExplicitEnum,
    ModelOutput,
    PaddingStrategy,
    PushToHubMixin,
    RepositoryNotFoundError,
    RevisionNotFoundError,
    TensorType,
    _LazyModule,
    add_code_sample_docstrings,
    add_end_docstrings,
    add_start_docstrings,
    add_start_docstrings_to_model_forward,
    cached_property,
    copy_func,
    default_cache_path,
    define_sagemaker_information,
    get_cached_models,
    get_file_from_repo,
    get_full_repo_name,
    get_torch_version,
    has_file,
    http_user_agent,
    is_apex_available,
    is_bsa_available,
    is_coloredlogs_available,
    is_datasets_available,
    is_detectrona_available,
    is_faiss_available,
    is_flax_available,
    is_ftfy_available,
    is_in_notebook,
    is_ipex_available,
    is_librosa_available,
    is_offline_mode,
    is_onnx_available,
    is_pandas_available,
    is_phonemizer_available,
    is_protobuf_available,
    is_psutil_available,
    is_pyanvml_available,
    is_pyctcdecode_available,
    is_pytesseract_available,
    is_pytorch_quantization_available,
    is_rjieba_available,
    is_sagemaker_dp_enabled,
    is_sagemaker_mp_enabled,
    is_scipy_available,
    is_sentencepiece_available,
    is_seqio_available,
    is_sklearn_available,
    is_soundfile_availble,
    is_spacy_available,
    is_speech_available,
    is_tensor,
    is_tensorflow_probability_available,
    is_tfaonnx_available,
    is_tf_available,
    is_timm_available,
    is_tokenizers_available,
    is_torch_available,
    is_torch_bfaa_available,
    is_torch_cuda_available,
    is_torch_fx_available,
    is_torch_fx_proxy,
    is_torch_mps_available,
    is_torch_tfaa_available,
    is_torch_tpu_available,
    is_torchaudio_available,
    is_training_run_on_sagemaker,
    is_vision_available,
    replace_return_docstrings,
    requires_backends,
    to_numpy,
    to_py_obj,
    torch_only_method,
)


'''simple docstring'''



import heapq as hq
import math
from collections.abc import Iterator




class   UpperCAmelCase_					:






						'''simple docstring'''






						def __init__( self   ,       _lowercase				):

												"""simple docstring"""



												_lowerCAmelCase  						=			str(id_				)
												_lowerCAmelCase  						=			None
												_lowerCAmelCase  						=			None
												_lowerCAmelCase  						=			[]
												_lowerCAmelCase  						=			{}  # {vertex:distance}




						def __lt__( self   ,       _lowercase				):

												"""simple docstring"""



												return self.key < other.key




						def __repr__( self				):

												"""simple docstring"""



												return self.id




						def  _lowercase     ( self   ,       _lowercase				):

												"""simple docstring"""



												self.neighbors.append(_lowercase				)




						def  _lowercase     ( self   ,       _lowercase   ,       _lowercase				):

												"""simple docstring"""



												_lowerCAmelCase  						=			weight






def A				(__lowerCamelCase				:List[Any]			,     __lowerCamelCase				:Union[str, Any]			,     __lowerCamelCase				:Dict			,     __lowerCamelCase				:Optional[int]		):
						# add the neighbors:
						graph[a - 1].add_neighbor(graph[b - 1]		)
						graph[b - 1].add_neighbor(graph[a - 1]		)
						# add the edges:
						graph[a - 1].add_edge(graph[b - 1]			,     __lowerCamelCase		)
						graph[b - 1].add_edge(graph[a - 1]			,     __lowerCamelCase		)


def A				(__lowerCamelCase				:list			,     __lowerCamelCase				:Vertex		):
						_lowerCAmelCase  						=			[]
						for u in graph:
												_lowerCAmelCase  						=			math.inf
												_lowerCAmelCase  						=			None
						_lowerCAmelCase  						=			0
						_lowerCAmelCase  						=			graph[:]
						while q:
												_lowerCAmelCase  						=			min(__lowerCamelCase		)
												q.remove(__lowerCamelCase		)
												for v in u.neighbors:
																		if (v in q) and (u.edges[v.id] < v.key):
																								_lowerCAmelCase  						=			u
																								_lowerCAmelCase  						=			u.edges[v.id]
						for i in range(1			,     len(__lowerCamelCase		)		):
												a.append((int(graph[i].id		) + 1, int(graph[i].pi.id		) + 1)		)
						return a


def A				(__lowerCamelCase				:list			,     __lowerCamelCase				:Vertex		):
						for u in graph:
												_lowerCAmelCase  						=			math.inf
												_lowerCAmelCase  						=			None
						_lowerCAmelCase  						=			0

						_lowerCAmelCase  						=			list(__lowerCamelCase		)
						hq.heapify(__lowerCamelCase		)

						while h:
												_lowerCAmelCase  						=			hq.heappop(__lowerCamelCase		)
												for v in u.neighbors:
																		if (v in h) and (u.edges[v.id] < v.key):
																								_lowerCAmelCase  						=			u
																								_lowerCAmelCase  						=			u.edges[v.id]
																								hq.heapify(__lowerCamelCase		)

						for i in range(1			,     len(__lowerCamelCase		)		):
												yield (int(graph[i].id		) + 1, int(graph[i].pi.id		) + 1)


def A				():
						pass


if __name__ == "__main__":
						import doctest

						doctest.testmod()
