
'''simple docstring'''



from __future__ import annotations
def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )       ->       tuple[float, float]:




   """simple docstring"""
   assert (
       c % greatest_common_divisor(SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  ) == 0
   )  # greatest_common_divisor(a,b) function implemented below
   ((_SCREAMING_SNAKE_CASE)	,							(_SCREAMING_SNAKE_CASE)	,							(_SCREAMING_SNAKE_CASE))       	=			extended_gcd(SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )  # extended_gcd(a,b) function implemented below
   _SCREAMING_SNAKE_CASE       	=			c / d
   return (r * x, r * y)
def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_ = 2  )       ->       None:




   """simple docstring"""
   ((_SCREAMING_SNAKE_CASE)	,							(_SCREAMING_SNAKE_CASE))       	=			diophantine(SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )  # Initial value
   _SCREAMING_SNAKE_CASE       	=			greatest_common_divisor(SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )
   _SCREAMING_SNAKE_CASE       	=			a // d
   _SCREAMING_SNAKE_CASE       	=			b // d

   for i in range(SCREAMING_SNAKE_CASE_  ):
      _SCREAMING_SNAKE_CASE       	=			xa + i * q
      _SCREAMING_SNAKE_CASE       	=			ya - i * p
      print(SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )
def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )       ->       int:




   """simple docstring"""
   if a < b:
      _SCREAMING_SNAKE_CASE	,							_SCREAMING_SNAKE_CASE       	=			b, a

   while a % b != 0:
      _SCREAMING_SNAKE_CASE	,							_SCREAMING_SNAKE_CASE       	=			b, a % b

   return b
def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )       ->       tuple[int, int, int]:




   """simple docstring"""
   assert a >= 0 and b >= 0

   if b == 0:
      _SCREAMING_SNAKE_CASE	,							_SCREAMING_SNAKE_CASE	,							_SCREAMING_SNAKE_CASE       	=			a, 1, 0
   else:
      ((_SCREAMING_SNAKE_CASE)	,							(_SCREAMING_SNAKE_CASE)	,							(_SCREAMING_SNAKE_CASE))       	=			extended_gcd(SCREAMING_SNAKE_CASE_      , a % b  )
      _SCREAMING_SNAKE_CASE       	=			q
      _SCREAMING_SNAKE_CASE       	=			p - q * (a // b)

   assert a % d == 0 and b % d == 0
   assert d == a * x + b * y

   return (d, x, y)


if __name__ == "__main__":
     from doctest import testmod

     testmod(name="diophantine", verbose=True)
     testmod(name="diophantine_all_soln", verbose=True)
     testmod(name="extended_gcd", verbose=True)
     testmod(name="greatest_common_divisor", verbose=True)








'''simple docstring'''



def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )       ->       Optional[int]:




   """simple docstring"""
   print("""\nVertex Distance"""  )
   for i in range(SCREAMING_SNAKE_CASE_  ):
      if dist[i] != float("""inf"""  ):
         print(SCREAMING_SNAKE_CASE_      , """\t"""      , int(dist[i]  )      , end="""\t"""  )
      else:
         print(SCREAMING_SNAKE_CASE_      , """\t"""      , """INF"""      , end="""\t"""  )
      print()
def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )       ->       Optional[Any]:




   """simple docstring"""
   _SCREAMING_SNAKE_CASE       	=			float("""inf"""  )
   _SCREAMING_SNAKE_CASE       	=			-1
   for i in range(SCREAMING_SNAKE_CASE_  ):
      if (not vset[i]) and mdist[i] < min_val:
         _SCREAMING_SNAKE_CASE       	=			i
         _SCREAMING_SNAKE_CASE       	=			mdist[i]
   return min_ind
def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )       ->       int:




   """simple docstring"""
   _SCREAMING_SNAKE_CASE       	=			[float("""inf"""  ) for _ in range(SCREAMING_SNAKE_CASE_  )]
   _SCREAMING_SNAKE_CASE       	=			[False for _ in range(SCREAMING_SNAKE_CASE_  )]
   _SCREAMING_SNAKE_CASE       	=			0.0

   for _ in range(v - 1  ):
      _SCREAMING_SNAKE_CASE       	=			min_dist(SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )
      _SCREAMING_SNAKE_CASE       	=			True

      for i in range(SCREAMING_SNAKE_CASE_  ):
         if (
             (not vset[i])
             and graph[u][i] != float("""inf"""  )
             and mdist[u] + graph[u][i] < mdist[i]
         ):
            _SCREAMING_SNAKE_CASE       	=			mdist[u] + graph[u][i]

   print_dist(SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )


if __name__ == "__main__":
     UpperCamelCase__ :						int    							=					int(input("Enter number of vertices: ").strip())
     UpperCamelCase__ :						Tuple    							=					int(input("Enter number of edges: ").strip())

     UpperCamelCase__ :						Optional[Any]    							=					[[float("inf") for i in range(V)] for j in range(V)]

     for i in range(V):
          UpperCamelCase__ :						int    							=					0.0

     for i in range(E):
          print("\nEdge ", i + 1)
          UpperCamelCase__ :						Union[str, Any]    							=					int(input("Enter source:").strip())
          UpperCamelCase__ :						Tuple    							=					int(input("Enter destination:").strip())
          UpperCamelCase__ :						Any    							=					float(input("Enter weight:").strip())
          UpperCamelCase__ :						List[Any]    							=					weight

     UpperCamelCase__ :						Optional[Any]    							=					int(input("\nEnter shortest path source:").strip())
     dijkstra(graph, V, gsrc)






