

from collections import Counter
from pathlib import Path
from typing import Optional, Tuple

import yaml





class A__    ( yaml.SafeLoader ):



 """simple docstring"""







 def    __magic_name__       (		self :	int     ,						A_ :	Tuple       ):






      '''simple docstring'''




      _lowerCAmelCase   :					Optional[Any]        =    [self.constructed_objects[key_node] for key_node, _ in node.value]
      _lowerCAmelCase   :					List[str]        =    [tuple(_A       ) if isinstance(_A     ,						_A       ) else key for key in keys]
      _lowerCAmelCase   :					Tuple        =    Counter(_A       )
      _lowerCAmelCase   :					Tuple        =    [key for key in counter if counter[key] > 1]
      if duplicate_keys:
           raise TypeError(F'''Got duplicate yaml keys: {duplicate_keys}'''       )


 def    __magic_name__       (		self :	Any     ,						A_ :	int     ,						A_ :	List[Any]=False       ):






      '''simple docstring'''




      _lowerCAmelCase   :					int        =    super().construct_mapping(_A     ,						deep=_A       )
      self._check_no_duplicates_on_constructed_node(_A       )
      return mapping







def 	_snake_case		(    SCREAMING_SNAKE_CASE				)       ->      Tuple[Optional[str], str]:

     """simple docstring"""







     _lowerCAmelCase   :					List[Any]        =    list(readme_content.splitlines()				)
     if full_content and full_content[0] == "---" and "---" in full_content[1:]:
          _lowerCAmelCase   :					List[str]        =    full_content[1:].index("---"				) + 1
          _lowerCAmelCase   :					List[str]        =    '\n'.join(full_content[1:sep_idx]				)
          return yamlblock, "\n".join(full_content[sep_idx + 1 :]				)

     return None, "\n".join(SCREAMING_SNAKE_CASE				)





class A__    ( snake_case__ ):



 """simple docstring"""







 _lowercase     :					int      =						{'''train_eval_index'''}  # train-eval-index in the YAML metadata

 @classmethod
 def    __magic_name__       (		cls :	Optional[int]     ,						A_ :	Union[str, Any]       ):






      '''simple docstring'''




      with open(_A     ,						encoding="utf-8"       ) as readme_file:
           _lowerCAmelCase   :					int        =    _split_yaml_from_readme(readme_file.read()       )
      if yaml_string is not None:
           return cls.from_yaml_string(_A       )
      else:
           return cls()

 def    __magic_name__       (		self :	Any     ,						A_ :	Optional[Any]       ):






      '''simple docstring'''




      if path.exists():
           with open(_A     ,						encoding="utf-8"       ) as readme_file:
                _lowerCAmelCase   :					Tuple        =    readme_file.read()
      else:
           _lowerCAmelCase   :					Dict        =    None
      _lowerCAmelCase   :					str        =    self._to_readme(_A       )
      with open(_A     ,						"w"     ,						encoding="utf-8"       ) as readme_file:
           readme_file.write(_A       )

 def    __magic_name__       (		self :	Union[str, Any]     ,						A_ :	Union[str, Any] = None       ):






      '''simple docstring'''




      if readme_content is not None:
           _lowerCAmelCase   :					str        =    _split_yaml_from_readme(_A       )
           _lowerCAmelCase   :					Dict        =    '---\n' + self.to_yaml_string() + '---\n' + content
      else:
           _lowerCAmelCase   :					Optional[Any]        =    '---\n' + self.to_yaml_string() + '---\n'
      return full_content

 @classmethod
 def    __magic_name__       (		cls :	Union[str, Any]     ,						A_ :	Dict       ):






      '''simple docstring'''




      _lowerCAmelCase   :					List[Any]        =    yaml.load(_A     ,						Loader=_NoDuplicateSafeLoader       ) or {}

      # Convert the YAML keys to DatasetMetadata fields
      _lowerCAmelCase   :					List[str]        =    {
          (key.replace("-"     ,						"_"       ) if key.replace("-"     ,						"_"       ) in cls._FIELDS_WITH_DASHES else key): value
          for key, value in metadata_dict.items()
      }
      return cls(**_A       )


 def    __magic_name__       (		self :	Optional[int]       ):






      '''simple docstring'''




      return yaml.safe_dump(
          {
              (key.replace("_"     ,						"-"       ) if key in self._FIELDS_WITH_DASHES else key): value
              for key, value in self.items()
          }     ,						sort_keys=_A     ,						allow_unicode=_A     ,						encoding="utf-8"     ,						).decode("utf-8"       )

SCREAMING_SNAKE_CASE__    				=     {
    '''image-classification''': [],
    '''translation''': [],
    '''image-segmentation''': [],
    '''fill-mask''': [],
    '''automatic-speech-recognition''': [],
    '''token-classification''': [],
    '''sentence-similarity''': [],
    '''audio-classification''': [],
    '''question-answering''': [],
    '''summarization''': [],
    '''zero-shot-classification''': [],
    '''table-to-text''': [],
    '''feature-extraction''': [],
    '''other''': [],
    '''multiple-choice''': [],
    '''text-classification''': [],
    '''text-to-image''': [],
    '''text2text-generation''': [],
    '''zero-shot-image-classification''': [],
    '''tabular-classification''': [],
    '''tabular-regression''': [],
    '''image-to-image''': [],
    '''tabular-to-text''': [],
    '''unconditional-image-generation''': [],
    '''text-retrieval''': [],
    '''text-to-speech''': [],
    '''object-detection''': [],
    '''audio-to-audio''': [],
    '''text-generation''': [],
    '''conversational''': [],
    '''table-question-answering''': [],
    '''visual-question-answering''': [],
    '''image-to-text''': [],
    '''reinforcement-learning''': [],
    '''voice-activity-detection''': [],
    '''time-series-forecasting''': [],
    '''document-question-answering''': [],
}


if __name__ == "__main__":
  from argparse import ArgumentParser

  SCREAMING_SNAKE_CASE__    				=     ArgumentParser(usage='Validate the yaml metadata block of a README.md file.')
  ap.add_argument('readme_filepath')
  SCREAMING_SNAKE_CASE__    				=     ap.parse_args()

  SCREAMING_SNAKE_CASE__    				=     Path(args.readme_filepath)
  SCREAMING_SNAKE_CASE__    				=     DatasetMetadata.from_readme(readme_filepath)
  print(dataset_metadata)
  dataset_metadata.to_readme(readme_filepath)









from __future__ import annotations







def 	_snake_case		(    SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)       ->      List[Any]:

     """simple docstring"""







     print(f'''Vertex\tShortest Distance from vertex {src}'''				)
     for i, d in enumerate(SCREAMING_SNAKE_CASE				):
          print(f'''{i}\t\t{d}'''				)







def 	_snake_case		(    SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)       ->      Tuple:

     """simple docstring"""







     for j in range(SCREAMING_SNAKE_CASE				):
          _lowerCAmelCase      ,			_lowerCAmelCase      ,			_lowerCAmelCase   :					Any        =    (graph[j][k] for k in ["src", "dst", "weight"])
          if distance[u] != float("inf"				) and distance[u] + w < distance[v]:
               return True
     return False







def 	_snake_case		(    SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)       ->      list[float]:

     """simple docstring"""







     _lowerCAmelCase   :					Tuple        =    [float("inf"				)] * vertex_count
     _lowerCAmelCase   :					int        =    0.0

     for _ in range(vertex_count - 1				):
          for j in range(SCREAMING_SNAKE_CASE				):
               _lowerCAmelCase      ,			_lowerCAmelCase      ,			_lowerCAmelCase   :					int        =    (graph[j][k] for k in ["src", "dst", "weight"])

               if distance[u] != float("inf"				) and distance[u] + w < distance[v]:
                    _lowerCAmelCase   :					List[str]        =    distance[u] + w

     _lowerCAmelCase   :					int        =    check_negative_cycle(SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE		,							SCREAMING_SNAKE_CASE				)
     if negative_cycle_exists:
          raise Exception("Negative cycle found"				)

     return distance


if __name__ == "__main__":
  import doctest

  doctest.testmod()

  __UpperCAmelCase    				=     int(input('Enter number of vertices: ').strip())
  __UpperCAmelCase    				=     int(input('Enter number of edges: ').strip())

  __UpperCAmelCase    				=     [{} for _ in range(E)]

  for i in range(E):
    print('Edge ', i + 1)
    __UpperCAmelCase				,__UpperCAmelCase				,__UpperCAmelCase    				=     (
        int(x)
        for x in input('Enter source, destination, weight: ').strip().split(' ')
    )
    __UpperCAmelCase    				=     {'src': src, 'dst': dest, 'weight': weight}

  __UpperCAmelCase    				=     int(input('\nEnter shortest path source:').strip())
  __UpperCAmelCase    				=     bellman_ford(graph, V, E, source)
  print_distance(shortest_distance, 0)






