






import heapq as hq
import math
from collections.abc import Iterator
class  lowerCAmelCase_       :




							def __init__(   self     :   str ,							SCREAMING_SNAKE_CASE_     :   List[str]	):
											lowerCAmelCase__      			=						str(id_	)
											lowerCAmelCase__      			=						None
											lowerCAmelCase__      			=						None
											lowerCAmelCase__      			=						[]
											lowerCAmelCase__      			=						{}  # {vertex:distance}




							def __lt__(   self     :   int ,							SCREAMING_SNAKE_CASE_     :   List[Any]	):
											return self.key < other.key




							def __repr__(   self     :   Optional[Any]	):
											return self.id




							def 						__snake_case					(   self     :   Tuple ,							SCREAMING_SNAKE_CASE_     :   Optional[int]	):
											self.neighbors.append(SCREAMING_SNAKE_CASE_	)




							def 						__snake_case					(   self     :   Tuple ,							SCREAMING_SNAKE_CASE_     :   str ,							SCREAMING_SNAKE_CASE_     :   List[Any]	):
											lowerCAmelCase__      			=						weight





def 	lowerCAmelCase_		(lowercase__						:       Any     ,					lowercase__						:       Optional[int]     ,					lowercase__						:       Any     ,					lowercase__						:       List[str]       )		->    List[Any]:


				'''simple docstring'''




				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]     ,					lowercase__       )
				graph[b - 1].add_edge(graph[a - 1]     ,					lowercase__       )





def 	lowerCAmelCase_		(lowercase__						:       list     ,					lowercase__						:       Vertex       )		->    list:


				'''simple docstring'''




				lowerCAmelCase__      			=						[]
				for u in graph:
								lowerCAmelCase__      			=						math.inf
								lowerCAmelCase__      			=						None
				lowerCAmelCase__      			=						0
				lowerCAmelCase__      			=						graph[:]
				while q:
								lowerCAmelCase__      			=						min(lowercase__       )
								q.remove(lowercase__       )
								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(lowercase__       )       ):
								a.append((int(graph[i].id       ) + 1, int(graph[i].pi.id       ) + 1)       )
				return a





def 	lowerCAmelCase_		(lowercase__						:       list     ,					lowercase__						:       Vertex       )		->    Iterator[tuple]:


				'''simple docstring'''




				for u in graph:
								lowerCAmelCase__      			=						math.inf
								lowerCAmelCase__      			=						None
				lowerCAmelCase__      			=						0

				lowerCAmelCase__      			=						list(lowercase__       )
				hq.heapify(lowercase__       )

				while h:
								lowerCAmelCase__      			=						hq.heappop(lowercase__       )
								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(lowercase__       )

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





def 	lowerCAmelCase_		()		->    None:


				'''simple docstring'''






if __name__ == "__main__":
			import doctest

			doctest.testmod()













from typing import TYPE_CHECKING

from ....utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


_UpperCAmelCase			:		Optional[Any]   				=    {
    "configuration_mctct": ["MCTCT_PRETRAINED_CONFIG_ARCHIVE_MAP", "MCTCTConfig"],
    "feature_extraction_mctct": ["MCTCTFeatureExtractor"],
    "processing_mctct": ["MCTCTProcessor"],
}


try:
			if not is_torch_available():
						raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
			pass
else:
			_UpperCAmelCase			:		str   				=    [
			    "MCTCT_PRETRAINED_MODEL_ARCHIVE_LIST",
			    "MCTCTForCTC",
			    "MCTCTModel",
			    "MCTCTPreTrainedModel",
			]


if TYPE_CHECKING:
			from .configuration_mctct import MCTCT_PRETRAINED_CONFIG_ARCHIVE_MAP, MCTCTConfig
			from .feature_extraction_mctct import MCTCTFeatureExtractor
			from .processing_mctct import MCTCTProcessor

			try:
						if not is_torch_available():
									raise OptionalDependencyNotAvailable()
			except OptionalDependencyNotAvailable:
						pass
			else:
						from .modeling_mctct import MCTCT_PRETRAINED_MODEL_ARCHIVE_LIST, MCTCTForCTC, MCTCTModel, MCTCTPreTrainedModel

else:
			import sys

			_UpperCAmelCase			:		List[str]   				=    _LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)





