
'''simple docstring'''


from __future__ import annotations



def 			__snake_case  (     _UpperCAmelCase       :							list[float],   _UpperCAmelCase       :							Optional[int]):
   print(f'Vertex\tShortest Distance from vertex {src}')
   for i, d in enumerate(UpperCamelCase__):
      print(f'{i}\t\t{d}')



def 			__snake_case  (     _UpperCAmelCase       :							list[dict[str, int]],   _UpperCAmelCase       :							list[float],   _UpperCAmelCase       :							int):
   for j in range(UpperCamelCase__):
      UpperCamelCase  ,			UpperCamelCase  ,			UpperCamelCase	  =	(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  (     _UpperCAmelCase       :							list[dict[str, int]],   _UpperCAmelCase       :							int,   _UpperCAmelCase       :							int,   _UpperCAmelCase       :							int):
   UpperCamelCase	  =	[float('''inf''')] * vertex_count
   UpperCamelCase	  =	0.0

   for _ in range(vertex_count - 1):
      for j in range(UpperCamelCase__):
         UpperCamelCase  ,			UpperCamelCase  ,			UpperCamelCase	  =	(graph[j][k] for k in ['''src''', '''dst''', '''weight'''])

         if distance[u] != float('''inf''') and distance[u] + w < distance[v]:
            UpperCamelCase	  =	distance[u] + w

   UpperCamelCase	  =	check_negative_cycle(UpperCamelCase__,   UpperCamelCase__,   UpperCamelCase__)
   if negative_cycle_exists:
      raise Exception('''Negative cycle found''')

   return distance


if __name__ == "__main__":
   import doctest

   doctest.testmod()

   snake_case_			:	List[Any] 	=       int(input('Enter number of vertices: ').strip())
   snake_case_			:	Dict 	=       int(input('Enter number of edges: ').strip())

   snake_case_			:	list[dict[str, int]] 	=       [{} for _ in range(E)]

   for i in range(E):
      print('Edge ', i + 1)
      snake_case_			:	Union[str, Any] 	=       (
          int(x)
          for x in input('Enter source, destination, weight: ').strip().split(' ')
      )
      snake_case_			:	Tuple 	=       {'src': src, 'dst': dest, 'weight': weight}

   snake_case_			:	List[Any] 	=       int(input('\nEnter shortest path source:').strip())
   snake_case_			:	List[Any] 	=       bellman_ford(graph, V, E, source)
   print_distance(shortest_distance, 0)












from typing import TYPE_CHECKING

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


a__: int							   =						{
    'configuration_m2m_100': ['M2M_100_PRETRAINED_CONFIG_ARCHIVE_MAP', 'M2M100Config', 'M2M100OnnxConfig'],
    'tokenization_m2m_100': ['M2M100Tokenizer'],
}


try:
       if not is_torch_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       a__: List[Any]							   =						[
           'M2M_100_PRETRAINED_MODEL_ARCHIVE_LIST',
           'M2M100ForConditionalGeneration',
           'M2M100Model',
           'M2M100PreTrainedModel',
       ]


if TYPE_CHECKING:
       from .configuration_mam_aaa import M2M_100_PRETRAINED_CONFIG_ARCHIVE_MAP, MaMaaaConfig, MaMaaaOnnxConfig
       from .tokenization_mam_aaa import MaMaaaTokenizer

       try:
              if not is_torch_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .modeling_mam_aaa import (
                  M2M_100_PRETRAINED_MODEL_ARCHIVE_LIST,
                  MaMaaaForConditionalGeneration,
                  MaMaaaModel,
                  MaMaaaPreTrainedModel,
              )


else:
       import sys

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





