


'''simple docstring'''





from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_flax_available,
    is_tf_available,
    is_torch_available,
)


UpperCAmelCase__     			=							{
    '''auto_factory''': ['''get_values'''],
    '''configuration_auto''': ['''ALL_PRETRAINED_CONFIG_ARCHIVE_MAP''', '''CONFIG_MAPPING''', '''MODEL_NAMES_MAPPING''', '''AutoConfig'''],
    '''feature_extraction_auto''': ['''FEATURE_EXTRACTOR_MAPPING''', '''AutoFeatureExtractor'''],
    '''image_processing_auto''': ['''IMAGE_PROCESSOR_MAPPING''', '''AutoImageProcessor'''],
    '''processing_auto''': ['''PROCESSOR_MAPPING''', '''AutoProcessor'''],
    '''tokenization_auto''': ['''TOKENIZER_MAPPING''', '''AutoTokenizer'''],
}

try:
  if not is_torch_available():
    raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
  pass
else:
  UpperCAmelCase__     			=							[
      '''MODEL_FOR_AUDIO_CLASSIFICATION_MAPPING''',
      '''MODEL_FOR_AUDIO_FRAME_CLASSIFICATION_MAPPING''',
      '''MODEL_FOR_AUDIO_XVECTOR_MAPPING''',
      '''MODEL_FOR_BACKBONE_MAPPING''',
      '''MODEL_FOR_CAUSAL_IMAGE_MODELING_MAPPING''',
      '''MODEL_FOR_CAUSAL_LM_MAPPING''',
      '''MODEL_FOR_CTC_MAPPING''',
      '''MODEL_FOR_DOCUMENT_QUESTION_ANSWERING_MAPPING''',
      '''MODEL_FOR_DEPTH_ESTIMATION_MAPPING''',
      '''MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING''',
      '''MODEL_FOR_IMAGE_SEGMENTATION_MAPPING''',
      '''MODEL_FOR_INSTANCE_SEGMENTATION_MAPPING''',
      '''MODEL_FOR_MASKED_IMAGE_MODELING_MAPPING''',
      '''MODEL_FOR_MASKED_LM_MAPPING''',
      '''MODEL_FOR_MASK_GENERATION_MAPPING''',
      '''MODEL_FOR_MULTIPLE_CHOICE_MAPPING''',
      '''MODEL_FOR_NEXT_SENTENCE_PREDICTION_MAPPING''',
      '''MODEL_FOR_OBJECT_DETECTION_MAPPING''',
      '''MODEL_FOR_PRETRAINING_MAPPING''',
      '''MODEL_FOR_QUESTION_ANSWERING_MAPPING''',
      '''MODEL_FOR_SEMANTIC_SEGMENTATION_MAPPING''',
      '''MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING''',
      '''MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING''',
      '''MODEL_FOR_SPEECH_SEQ_2_SEQ_MAPPING''',
      '''MODEL_FOR_TABLE_QUESTION_ANSWERING_MAPPING''',
      '''MODEL_FOR_TEXT_ENCODING_MAPPING''',
      '''MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING''',
      '''MODEL_FOR_UNIVERSAL_SEGMENTATION_MAPPING''',
      '''MODEL_FOR_VIDEO_CLASSIFICATION_MAPPING''',
      '''MODEL_FOR_VISION_2_SEQ_MAPPING''',
      '''MODEL_FOR_VISUAL_QUESTION_ANSWERING_MAPPING''',
      '''MODEL_MAPPING''',
      '''MODEL_WITH_LM_HEAD_MAPPING''',
      '''MODEL_FOR_ZERO_SHOT_IMAGE_CLASSIFICATION_MAPPING''',
      '''MODEL_FOR_ZERO_SHOT_OBJECT_DETECTION_MAPPING''',
      '''AutoModel''',
      '''AutoBackbone''',
      '''AutoModelForAudioClassification''',
      '''AutoModelForAudioFrameClassification''',
      '''AutoModelForAudioXVector''',
      '''AutoModelForCausalLM''',
      '''AutoModelForCTC''',
      '''AutoModelForDepthEstimation''',
      '''AutoModelForImageClassification''',
      '''AutoModelForImageSegmentation''',
      '''AutoModelForInstanceSegmentation''',
      '''AutoModelForMaskGeneration''',
      '''AutoModelForTextEncoding''',
      '''AutoModelForMaskedImageModeling''',
      '''AutoModelForMaskedLM''',
      '''AutoModelForMultipleChoice''',
      '''AutoModelForNextSentencePrediction''',
      '''AutoModelForObjectDetection''',
      '''AutoModelForPreTraining''',
      '''AutoModelForQuestionAnswering''',
      '''AutoModelForSemanticSegmentation''',
      '''AutoModelForSeq2SeqLM''',
      '''AutoModelForSequenceClassification''',
      '''AutoModelForSpeechSeq2Seq''',
      '''AutoModelForTableQuestionAnswering''',
      '''AutoModelForTokenClassification''',
      '''AutoModelForUniversalSegmentation''',
      '''AutoModelForVideoClassification''',
      '''AutoModelForVision2Seq''',
      '''AutoModelForVisualQuestionAnswering''',
      '''AutoModelForDocumentQuestionAnswering''',
      '''AutoModelWithLMHead''',
      '''AutoModelForZeroShotImageClassification''',
      '''AutoModelForZeroShotObjectDetection''',
  ]

try:
  if not is_tf_available():
    raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
  pass
else:
  UpperCAmelCase__     			=							[
      '''TF_MODEL_FOR_AUDIO_CLASSIFICATION_MAPPING''',
      '''TF_MODEL_FOR_CAUSAL_LM_MAPPING''',
      '''TF_MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING''',
      '''TF_MODEL_FOR_MASK_GENERATION_MAPPING''',
      '''TF_MODEL_FOR_MASKED_IMAGE_MODELING_MAPPING''',
      '''TF_MODEL_FOR_MASKED_LM_MAPPING''',
      '''TF_MODEL_FOR_MULTIPLE_CHOICE_MAPPING''',
      '''TF_MODEL_FOR_NEXT_SENTENCE_PREDICTION_MAPPING''',
      '''TF_MODEL_FOR_PRETRAINING_MAPPING''',
      '''TF_MODEL_FOR_QUESTION_ANSWERING_MAPPING''',
      '''TF_MODEL_FOR_DOCUMENT_QUESTION_ANSWERING_MAPPING''',
      '''TF_MODEL_FOR_SEMANTIC_SEGMENTATION_MAPPING''',
      '''TF_MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING''',
      '''TF_MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING''',
      '''TF_MODEL_FOR_SPEECH_SEQ_2_SEQ_MAPPING''',
      '''TF_MODEL_FOR_TABLE_QUESTION_ANSWERING_MAPPING''',
      '''TF_MODEL_FOR_TEXT_ENCODING_MAPPING''',
      '''TF_MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING''',
      '''TF_MODEL_FOR_VISION_2_SEQ_MAPPING''',
      '''TF_MODEL_FOR_ZERO_SHOT_IMAGE_CLASSIFICATION_MAPPING''',
      '''TF_MODEL_MAPPING''',
      '''TF_MODEL_WITH_LM_HEAD_MAPPING''',
      '''TFAutoModel''',
      '''TFAutoModelForAudioClassification''',
      '''TFAutoModelForCausalLM''',
      '''TFAutoModelForImageClassification''',
      '''TFAutoModelForMaskedImageModeling''',
      '''TFAutoModelForMaskedLM''',
      '''TFAutoModelForMaskGeneration''',
      '''TFAutoModelForMultipleChoice''',
      '''TFAutoModelForNextSentencePrediction''',
      '''TFAutoModelForPreTraining''',
      '''TFAutoModelForDocumentQuestionAnswering''',
      '''TFAutoModelForQuestionAnswering''',
      '''TFAutoModelForSemanticSegmentation''',
      '''TFAutoModelForSeq2SeqLM''',
      '''TFAutoModelForSequenceClassification''',
      '''TFAutoModelForSpeechSeq2Seq''',
      '''TFAutoModelForTableQuestionAnswering''',
      '''TFAutoModelForTextEncoding''',
      '''TFAutoModelForTokenClassification''',
      '''TFAutoModelForVision2Seq''',
      '''TFAutoModelForZeroShotImageClassification''',
      '''TFAutoModelWithLMHead''',
  ]

try:
  if not is_flax_available():
    raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
  pass
else:
  UpperCAmelCase__     			=							[
      '''FLAX_MODEL_FOR_AUDIO_CLASSIFICATION_MAPPING''',
      '''FLAX_MODEL_FOR_CAUSAL_LM_MAPPING''',
      '''FLAX_MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING''',
      '''FLAX_MODEL_FOR_MASKED_LM_MAPPING''',
      '''FLAX_MODEL_FOR_MULTIPLE_CHOICE_MAPPING''',
      '''FLAX_MODEL_FOR_NEXT_SENTENCE_PREDICTION_MAPPING''',
      '''FLAX_MODEL_FOR_PRETRAINING_MAPPING''',
      '''FLAX_MODEL_FOR_QUESTION_ANSWERING_MAPPING''',
      '''FLAX_MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING''',
      '''FLAX_MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING''',
      '''FLAX_MODEL_FOR_SPEECH_SEQ_2_SEQ_MAPPING''',
      '''FLAX_MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING''',
      '''FLAX_MODEL_FOR_VISION_2_SEQ_MAPPING''',
      '''FLAX_MODEL_MAPPING''',
      '''FlaxAutoModel''',
      '''FlaxAutoModelForCausalLM''',
      '''FlaxAutoModelForImageClassification''',
      '''FlaxAutoModelForMaskedLM''',
      '''FlaxAutoModelForMultipleChoice''',
      '''FlaxAutoModelForNextSentencePrediction''',
      '''FlaxAutoModelForPreTraining''',
      '''FlaxAutoModelForQuestionAnswering''',
      '''FlaxAutoModelForSeq2SeqLM''',
      '''FlaxAutoModelForSequenceClassification''',
      '''FlaxAutoModelForSpeechSeq2Seq''',
      '''FlaxAutoModelForTokenClassification''',
      '''FlaxAutoModelForVision2Seq''',
  ]


if TYPE_CHECKING:
  from .auto_factory import get_values
  from .configuration_auto import ALL_PRETRAINED_CONFIG_ARCHIVE_MAP, CONFIG_MAPPING, MODEL_NAMES_MAPPING, AutoConfig
  from .feature_extraction_auto import FEATURE_EXTRACTOR_MAPPING, AutoFeatureExtractor
  from .image_processing_auto import IMAGE_PROCESSOR_MAPPING, AutoImageProcessor
  from .processing_auto import PROCESSOR_MAPPING, AutoProcessor
  from .tokenization_auto import TOKENIZER_MAPPING, AutoTokenizer

  try:
    if not is_torch_available():
      raise OptionalDependencyNotAvailable()
  except OptionalDependencyNotAvailable:
    pass
  else:
    from .modeling_auto import (
        MODEL_FOR_AUDIO_CLASSIFICATION_MAPPING,
        MODEL_FOR_AUDIO_FRAME_CLASSIFICATION_MAPPING,
        MODEL_FOR_AUDIO_XVECTOR_MAPPING,
        MODEL_FOR_BACKBONE_MAPPING,
        MODEL_FOR_CAUSAL_IMAGE_MODELING_MAPPING,
        MODEL_FOR_CAUSAL_LM_MAPPING,
        MODEL_FOR_CTC_MAPPING,
        MODEL_FOR_DEPTH_ESTIMATION_MAPPING,
        MODEL_FOR_DOCUMENT_QUESTION_ANSWERING_MAPPING,
        MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING,
        MODEL_FOR_IMAGE_SEGMENTATION_MAPPING,
        MODEL_FOR_INSTANCE_SEGMENTATION_MAPPING,
        MODEL_FOR_MASK_GENERATION_MAPPING,
        MODEL_FOR_MASKED_IMAGE_MODELING_MAPPING,
        MODEL_FOR_MASKED_LM_MAPPING,
        MODEL_FOR_MULTIPLE_CHOICE_MAPPING,
        MODEL_FOR_NEXT_SENTENCE_PREDICTION_MAPPING,
        MODEL_FOR_OBJECT_DETECTION_MAPPING,
        MODEL_FOR_PRETRAINING_MAPPING,
        MODEL_FOR_QUESTION_ANSWERING_MAPPING,
        MODEL_FOR_SEMANTIC_SEGMENTATION_MAPPING,
        MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING,
        MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING,
        MODEL_FOR_SPEECH_SEQ_2_SEQ_MAPPING,
        MODEL_FOR_TABLE_QUESTION_ANSWERING_MAPPING,
        MODEL_FOR_TEXT_ENCODING_MAPPING,
        MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING,
        MODEL_FOR_UNIVERSAL_SEGMENTATION_MAPPING,
        MODEL_FOR_VIDEO_CLASSIFICATION_MAPPING,
        MODEL_FOR_VISION_2_SEQ_MAPPING,
        MODEL_FOR_VISUAL_QUESTION_ANSWERING_MAPPING,
        MODEL_FOR_ZERO_SHOT_IMAGE_CLASSIFICATION_MAPPING,
        MODEL_FOR_ZERO_SHOT_OBJECT_DETECTION_MAPPING,
        MODEL_MAPPING,
        MODEL_WITH_LM_HEAD_MAPPING,
        AutoBackbone,
        AutoModel,
        AutoModelForAudioClassification,
        AutoModelForAudioFrameClassification,
        AutoModelForAudioXVector,
        AutoModelForCausalLM,
        AutoModelForCTC,
        AutoModelForDepthEstimation,
        AutoModelForDocumentQuestionAnswering,
        AutoModelForImageClassification,
        AutoModelForImageSegmentation,
        AutoModelForInstanceSegmentation,
        AutoModelForMaskedImageModeling,
        AutoModelForMaskedLM,
        AutoModelForMaskGeneration,
        AutoModelForMultipleChoice,
        AutoModelForNextSentencePrediction,
        AutoModelForObjectDetection,
        AutoModelForPreTraining,
        AutoModelForQuestionAnswering,
        AutoModelForSemanticSegmentation,
        AutoModelForSeqaSeqLM,
        AutoModelForSequenceClassification,
        AutoModelForSpeechSeqaSeq,
        AutoModelForTableQuestionAnswering,
        AutoModelForTextEncoding,
        AutoModelForTokenClassification,
        AutoModelForUniversalSegmentation,
        AutoModelForVideoClassification,
        AutoModelForVisionaSeq,
        AutoModelForVisualQuestionAnswering,
        AutoModelForZeroShotImageClassification,
        AutoModelForZeroShotObjectDetection,
        AutoModelWithLMHead,
    )

  try:
    if not is_tf_available():
      raise OptionalDependencyNotAvailable()
  except OptionalDependencyNotAvailable:
    pass
  else:
    from .modeling_tf_auto import (
        TF_MODEL_FOR_AUDIO_CLASSIFICATION_MAPPING,
        TF_MODEL_FOR_CAUSAL_LM_MAPPING,
        TF_MODEL_FOR_DOCUMENT_QUESTION_ANSWERING_MAPPING,
        TF_MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING,
        TF_MODEL_FOR_MASK_GENERATION_MAPPING,
        TF_MODEL_FOR_MASKED_IMAGE_MODELING_MAPPING,
        TF_MODEL_FOR_MASKED_LM_MAPPING,
        TF_MODEL_FOR_MULTIPLE_CHOICE_MAPPING,
        TF_MODEL_FOR_NEXT_SENTENCE_PREDICTION_MAPPING,
        TF_MODEL_FOR_PRETRAINING_MAPPING,
        TF_MODEL_FOR_QUESTION_ANSWERING_MAPPING,
        TF_MODEL_FOR_SEMANTIC_SEGMENTATION_MAPPING,
        TF_MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING,
        TF_MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING,
        TF_MODEL_FOR_SPEECH_SEQ_2_SEQ_MAPPING,
        TF_MODEL_FOR_TABLE_QUESTION_ANSWERING_MAPPING,
        TF_MODEL_FOR_TEXT_ENCODING_MAPPING,
        TF_MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING,
        TF_MODEL_FOR_VISION_2_SEQ_MAPPING,
        TF_MODEL_FOR_ZERO_SHOT_IMAGE_CLASSIFICATION_MAPPING,
        TF_MODEL_MAPPING,
        TF_MODEL_WITH_LM_HEAD_MAPPING,
        TFAutoModel,
        TFAutoModelForAudioClassification,
        TFAutoModelForCausalLM,
        TFAutoModelForDocumentQuestionAnswering,
        TFAutoModelForImageClassification,
        TFAutoModelForMaskedImageModeling,
        TFAutoModelForMaskedLM,
        TFAutoModelForMaskGeneration,
        TFAutoModelForMultipleChoice,
        TFAutoModelForNextSentencePrediction,
        TFAutoModelForPreTraining,
        TFAutoModelForQuestionAnswering,
        TFAutoModelForSemanticSegmentation,
        TFAutoModelForSeqaSeqLM,
        TFAutoModelForSequenceClassification,
        TFAutoModelForSpeechSeqaSeq,
        TFAutoModelForTableQuestionAnswering,
        TFAutoModelForTextEncoding,
        TFAutoModelForTokenClassification,
        TFAutoModelForVisionaSeq,
        TFAutoModelForZeroShotImageClassification,
        TFAutoModelWithLMHead,
    )

  try:
    if not is_flax_available():
      raise OptionalDependencyNotAvailable()
  except OptionalDependencyNotAvailable:
    pass
  else:
    from .modeling_flax_auto import (
        FLAX_MODEL_FOR_AUDIO_CLASSIFICATION_MAPPING,
        FLAX_MODEL_FOR_CAUSAL_LM_MAPPING,
        FLAX_MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING,
        FLAX_MODEL_FOR_MASKED_LM_MAPPING,
        FLAX_MODEL_FOR_MULTIPLE_CHOICE_MAPPING,
        FLAX_MODEL_FOR_NEXT_SENTENCE_PREDICTION_MAPPING,
        FLAX_MODEL_FOR_PRETRAINING_MAPPING,
        FLAX_MODEL_FOR_QUESTION_ANSWERING_MAPPING,
        FLAX_MODEL_FOR_SEQ_TO_SEQ_CAUSAL_LM_MAPPING,
        FLAX_MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING,
        FLAX_MODEL_FOR_SPEECH_SEQ_2_SEQ_MAPPING,
        FLAX_MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING,
        FLAX_MODEL_FOR_VISION_2_SEQ_MAPPING,
        FLAX_MODEL_MAPPING,
        FlaxAutoModel,
        FlaxAutoModelForCausalLM,
        FlaxAutoModelForImageClassification,
        FlaxAutoModelForMaskedLM,
        FlaxAutoModelForMultipleChoice,
        FlaxAutoModelForNextSentencePrediction,
        FlaxAutoModelForPreTraining,
        FlaxAutoModelForQuestionAnswering,
        FlaxAutoModelForSeqaSeqLM,
        FlaxAutoModelForSequenceClassification,
        FlaxAutoModelForSpeechSeqaSeq,
        FlaxAutoModelForTokenClassification,
        FlaxAutoModelForVisionaSeq,
    )

else:
  import sys

  UpperCAmelCase__     			=							_LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)





from collections import deque
def        UpperCAmelCase_      (							__snake_case		)  ->    Any:







 """simple docstring"""


 return input(__snake_case		).strip().split(''' '''		)
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case		)  ->    dict[int, list[int]]:







 """simple docstring"""


 _lowercase							   ={}
 for i in range(__snake_case		):
  _lowercase							   =[]

 for e in range(__snake_case		):
  _lowercase   ,					_lowercase							   =(int(__snake_case		) for i in _input(F"Edge {e + 1}: <node1> <node2> "		))
  graph[x].append(__snake_case		)
 return graph
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case		)  ->    dict[int, list[int]]:







 """simple docstring"""


 _lowercase							   ={}
 for i in range(__snake_case		):
  _lowercase							   =[]

 for e in range(__snake_case		):
  _lowercase   ,					_lowercase							   =(int(__snake_case		) for i in _input(F"Edge {e + 1}: <node1> <node2> "		))
  graph[x].append(__snake_case		)
  graph[y].append(__snake_case		)
 return graph
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case		)  ->    dict[int, list[tuple[int, int]]]:







 """simple docstring"""


 _lowercase							   ={}
 for i in range(__snake_case		):
  _lowercase							   =[]

 for e in range(__snake_case		):
  _lowercase   ,					_lowercase   ,					_lowercase							   =(int(__snake_case		) for i in _input(F"Edge {e + 1}: <node1> <node2> <weight> "		))
  graph[x].append((y, w)		)
  graph[y].append((x, w)		)
 return graph


if __name__ == "__main__":
  UpperCAmelCase__			,UpperCAmelCase__     			=							(int(i) for i in _input('''Number of nodes and edges: '''))

  UpperCAmelCase__     			=							int(
      _input(
          '''Press 1 or 2 or 3 \n'''
          '''1. Unweighted directed \n'''
          '''2. Unweighted undirected \n'''
          '''3. Weighted undirected \n'''
      )[0]
  )

  UpperCAmelCase__     			=							{
      1: initialize_unweighted_directed_graph,
      2: initialize_unweighted_undirected_graph,
      3: initialize_weighted_undirected_graph,
  }[graph_choice](n, m)
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case		)  ->    Tuple:







 """simple docstring"""


 _lowercase   ,					_lowercase							   ={s}, [s]
 print(__snake_case		)
 while _s:
  _lowercase							   =0
  for i in g[_s[-1]]:
   if i not in vis:
    _s.append(__snake_case		)
    vis.add(__snake_case		)
    _lowercase							   =1
    print(__snake_case		)
    break
  if not flag:
   _s.pop()
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case		)  ->    int:







 """simple docstring"""


 _lowercase   ,					_lowercase							   ={s}, deque([s]		)
 print(__snake_case		)
 while q:
  _lowercase							   =q.popleft()
  for v in g[u]:
   if v not in vis:
    vis.add(__snake_case		)
    q.append(__snake_case		)
    print(__snake_case		)
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case		)  ->    Optional[int]:







 """simple docstring"""


 _lowercase   ,					_lowercase   ,					_lowercase							   ={s: 0}, set(), {s: 0}
 while True:
  if len(__snake_case		) == len(__snake_case		) - 1:
   break
  _lowercase							   =100000
  for i in dist:
   if i not in known and dist[i] < mini:
    _lowercase							   =dist[i]
    _lowercase							   =i
  known.add(__snake_case		)
  for v in g[u]:
   if v[0] not in known and dist[u] + v[1] < dist.get(v[0]  ,		100000		):
    _lowercase							   =dist[u] + v[1]
    _lowercase							   =u
 for i in dist:
  if i != s:
   print(dist[i]		)
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case=None  ,		__snake_case=None		)  ->    Tuple:







 """simple docstring"""


 if q is None:
  _lowercase							   =[1]
 if ind is None:
  _lowercase							   =[0] * (len(__snake_case		) + 1)  # SInce oth Index is ignored
  for u in g:
   for v in g[u]:
    ind[v] += 1
  _lowercase							   =deque()
  for i in g:
   if ind[i] == 0:
    q.append(__snake_case		)
 if len(__snake_case		) == 0:
  return
 _lowercase							   =q.popleft()
 print(__snake_case		)
 for w in g[v]:
  ind[w] -= 1
  if ind[w] == 0:
   q.append(__snake_case		)
 topo(__snake_case  ,		__snake_case  ,		__snake_case		)
def        UpperCAmelCase_      (							)  ->    Tuple:







 """simple docstring"""


 _lowercase							   =input().strip()
 _lowercase							   =[]
 for _ in range(__snake_case		):
  a.append(map(__snake_case  ,		input().strip().split()		)		)
 return a, n
def        UpperCAmelCase_      (							__snake_case		)  ->    Any:







 """simple docstring"""


 ((_lowercase)   ,					(_lowercase))							   =a_and_n
 _lowercase							   =list(__snake_case		)
 _lowercase							   =[[0] * n for i in range(__snake_case		)]
 for k in range(__snake_case		):
  for i in range(__snake_case		):
   for j in range(__snake_case		):
    if dist[i][j] > dist[i][k] + dist[k][j]:
     _lowercase							   =dist[i][k] + dist[k][j]
     _lowercase							   =k
 print(__snake_case		)
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case		)  ->    Optional[Any]:







 """simple docstring"""


 _lowercase   ,					_lowercase   ,					_lowercase							   ={s: 0}, set(), {s: 0}
 while True:
  if len(__snake_case		) == len(__snake_case		) - 1:
   break
  _lowercase							   =100000
  for i in dist:
   if i not in known and dist[i] < mini:
    _lowercase							   =dist[i]
    _lowercase							   =i
  known.add(__snake_case		)
  for v in g[u]:
   if v[0] not in known and v[1] < dist.get(v[0]  ,		100000		):
    _lowercase							   =v[1]
    _lowercase							   =u
 return dist
def        UpperCAmelCase_      (							)  ->    Dict:







 """simple docstring"""


 _lowercase   ,					_lowercase							   =map(__snake_case  ,		input().split(''' '''		)		)
 _lowercase							   =[]
 for _ in range(__snake_case		):
  edges.append(map(__snake_case  ,		input().split(''' '''		)		)		)
 return edges, n
def        UpperCAmelCase_      (							__snake_case		)  ->    str:







 """simple docstring"""


 ((_lowercase)   ,					(_lowercase))							   =e_and_n
 e.sort(reverse=__snake_case  ,		key=lambda __snake_case		: x[2]		)
 _lowercase							   =[{i} for i in range(1  ,		n + 1		)]
 while True:
  if len(__snake_case		) == 1:
   break
  print(__snake_case		)
  _lowercase							   =e.pop()
  for i in range(len(__snake_case		)		):
   if x[0] in s[i]:
    break
  for j in range(len(__snake_case		)		):
   if x[1] in s[j]:
    if i == j:
     break
    s[j].update(s[i]		)
    s.pop(__snake_case		)
    break



def        UpperCAmelCase_      (							__snake_case		)  ->    Tuple:







 """simple docstring"""


 _lowercase							   =[]
 for node in graph:
  if not graph[node]:
   isolated.append(__snake_case		)
 return isolated

