
'''simple docstring'''



from collections import namedtuple

UpperCamelCase__ :						List[Any]    							=					namedtuple("from_to", "from_ to")

UpperCamelCase__ :						List[Any]    							=					{
    "millimeter": "mm",
    "centimeter": "cm",
    "meter": "m",
    "kilometer": "km",
    "inch": "in",
    "inche": "in",  # Trailing 's' has been stripped off
    "feet": "ft",
    "foot": "ft",
    "yard": "yd",
    "mile": "mi",
}

UpperCamelCase__ :						Optional[Any]    							=					{
    "mm": from_to(0.001, 1_000),
    "cm": from_to(0.01, 100),
    "m": from_to(1, 1),
    "km": from_to(1_000, 0.001),
    "in": from_to(0.0_254, 39.3_701),
    "ft": from_to(0.3_048, 3.28_084),
    "yd": from_to(0.9_144, 1.09_361),
    "mi": from_to(1_609.34, 0.000_621_371),
}
def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )       ->       float:




   """simple docstring"""
   _SCREAMING_SNAKE_CASE       	=			from_type.lower().rstrip("""s"""  )
   _SCREAMING_SNAKE_CASE       	=			TYPE_CONVERSION.get(SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )
   _SCREAMING_SNAKE_CASE       	=			to_type.lower().rstrip("""s"""  )
   _SCREAMING_SNAKE_CASE       	=			TYPE_CONVERSION.get(SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )
   if new_from not in METRIC_CONVERSION:
      _SCREAMING_SNAKE_CASE       	=			(
          F"Invalid 'from_type' value: {from_type!r}.\n"
          F"Conversion abbreviations are: {', '.join(SCREAMING_SNAKE_CASE_  )}"
      )
      raise ValueError(SCREAMING_SNAKE_CASE_  )
   if new_to not in METRIC_CONVERSION:
      _SCREAMING_SNAKE_CASE       	=			(
          F"Invalid 'to_type' value: {to_type!r}.\n"
          F"Conversion abbreviations are: {', '.join(SCREAMING_SNAKE_CASE_  )}"
      )
      raise ValueError(SCREAMING_SNAKE_CASE_  )
   return value * METRIC_CONVERSION[new_from].from_ * METRIC_CONVERSION[new_to].to


if __name__ == "__main__":
     import doctest

     doctest.testmod()








'''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)






