



'''simple docstring'''


from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

lowercase							       =			TypeVar('''KEY''')
lowercase							       =			TypeVar('''VAL''')







@dataclass(frozen=__a					,	slots=__a)
class 	UpperCAmelCase	(		Generic[KEY, VAL]):


 '''simple docstring'''




 __magic_name__					: KEY
 __magic_name__					: VAL







class 	UpperCAmelCase	(		_Item):


 '''simple docstring'''




 def __init__(   self) ->      None:



      """simple docstring"""







      super().__init__(lowerCAmelCase_							,  lowerCAmelCase_)




 def __bool__(   self) ->      bool:



      """simple docstring"""







      return False



lowercase							       =			_DeletedItem()







class 	UpperCAmelCase	(		MutableMapping[KEY, VAL]):


 '''simple docstring'''




 def __init__(   self							,  lowerCAmelCase_ = 8							,  lowerCAmelCase_ = 0.7_5) ->      None:



      """simple docstring"""







      a_       		=initial_block_size
      a_       		=[None] * initial_block_size
      assert 0.0 < capacity_factor < 1.0
      a_       		=capacity_factor
      a_       		=0




 def       lowercase_  (   self							,  lowerCAmelCase_) ->      int:



      """simple docstring"""







      return hash(lowerCAmelCase_) % len(self._buckets)




 def       lowercase_  (   self							,  lowerCAmelCase_) ->      int:



      """simple docstring"""







      return (ind + 1) % len(self._buckets)




 def       lowercase_  (   self							,  lowerCAmelCase_							,  lowerCAmelCase_							,  lowerCAmelCase_) ->      bool:



      """simple docstring"""







      a_       		=self._buckets[ind]
      if not stored:
           a_       		=_Item(lowerCAmelCase_							,  lowerCAmelCase_)
           self._len += 1
           return True
      elif stored.key == key:
           a_       		=_Item(lowerCAmelCase_							,  lowerCAmelCase_)
           return True
      else:
           return False




 def       lowercase_  (   self) ->      bool:



      """simple docstring"""







      a_       		=len(self._buckets) * self._capacity_factor
      return len(self) >= int(lowerCAmelCase_)




 def       lowercase_  (   self) ->      bool:



      """simple docstring"""







      if len(self._buckets) <= self._initial_block_size:
           return False
      a_       		=len(self._buckets) * self._capacity_factor / 2
      return len(self) < limit




 def       lowercase_  (   self							,  lowerCAmelCase_) ->      None:



      """simple docstring"""







      a_       		=self._buckets
      a_       		=[None] * new_size
      a_       		=0
      for item in old_buckets:
           if item:
                self._add_item(item.key							,  item.val)




 def       lowercase_  (   self) ->      None:



      """simple docstring"""







      self._resize(len(self._buckets) * 2)




 def       lowercase_  (   self) ->      None:



      """simple docstring"""







      self._resize(len(self._buckets) // 2)




 def       lowercase_  (   self							,  lowerCAmelCase_) ->      Iterator[int]:



      """simple docstring"""







      a_       		=self._get_bucket_index(lowerCAmelCase_)
      for _ in range(len(self._buckets)):
           yield ind
           a_       		=self._get_next_ind(lowerCAmelCase_)




 def       lowercase_  (   self							,  lowerCAmelCase_							,  lowerCAmelCase_) ->      None:



      """simple docstring"""







      for ind in self._iterate_buckets(lowerCAmelCase_):
           if self._try_set(lowerCAmelCase_							,  lowerCAmelCase_							,  lowerCAmelCase_):
                break




 def __setitem__(   self							,  lowerCAmelCase_							,  lowerCAmelCase_) ->      None:



      """simple docstring"""







      if self._is_full():
           self._size_up()

      self._add_item(lowerCAmelCase_							,  lowerCAmelCase_)




 def __delitem__(   self							,  lowerCAmelCase_) ->      None:



      """simple docstring"""







      for ind in self._iterate_buckets(lowerCAmelCase_):
           a_       		=self._buckets[ind]
           if item is None:
                raise KeyError(lowerCAmelCase_)
           if item is _deleted:
                continue
           if item.key == key:
                a_       		=_deleted
                self._len -= 1
                break
      if self._is_sparse():
           self._size_down()




 def __getitem__(   self							,  lowerCAmelCase_) ->      VAL:



      """simple docstring"""







      for ind in self._iterate_buckets(lowerCAmelCase_):
           a_       		=self._buckets[ind]
           if item is None:
                break
           if item is _deleted:
                continue
           if item.key == key:
                return item.val
      raise KeyError(lowerCAmelCase_)




 def __len__(   self) ->      int:



      """simple docstring"""







      return self._len




 def __iter__(   self) ->      Iterator[KEY]:



      """simple docstring"""







      yield from (item.key for item in self._buckets if item)




 def __repr__(   self) ->      str:



      """simple docstring"""







      a_       		=" ,".join(
          f"""{item.key}: {item.val}""" for item in self._buckets if item)
      return f"""HashMap({val_string})"""







'''simple docstring'''


from __future__ import annotations






def  UpperCAmelCase_       (		lowercase__       ,	lowercase__       ):


     '''simple docstring'''







     print(F"""Vertex\tShortest Distance from vertex {src}"""       )
     for i, d in enumerate(lowercase__       ):
          print(F"""{i}\t\t{d}"""       )






def  UpperCAmelCase_       (		lowercase__       ,	lowercase__       ,	lowercase__       ):


     '''simple docstring'''







     for j in range(lowercase__       ):
          a_		,						a_		,						a_       		=(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  UpperCAmelCase_       (		lowercase__       ,	lowercase__       ,	lowercase__       ,	lowercase__       ):


     '''simple docstring'''







     a_       		=[float("inf"       )] * vertex_count
     a_       		=0.0

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

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

     a_       		=check_negative_cycle(lowercase__       ,	lowercase__       ,	lowercase__       )
     if negative_cycle_exists:
          raise Exception("Negative cycle found"       )

     return distance


if __name__ == "__main__":
  import doctest

  doctest.testmod()

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

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

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

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


