

from __future__ import annotations

from typing import Any





class       __UpperCAmelCase  :



   def __init__(							self							:  Union[str, Any],	__A							:  Any,	__A							:  Any		):  # noqa: A002
     UpperCAmelCase :							List[str]								=				item
     UpperCAmelCase :							List[str]								=				next






class       __UpperCAmelCase  :



   def __init__(							self							:  Dict		):
     UpperCAmelCase :							Node | None								=				None
     UpperCAmelCase :							Tuple								=				0



   def  __magic_name__					(							self							:  int,	__A							:  Any		):
     UpperCAmelCase :							str								=				Node(__A,	self.head		)
     self.size += 1



   def  __magic_name__					(							self							:  Union[str, Any]		):
     # Switched 'self.is_empty()' to 'self.head is None'
     # because mypy was considering the possibility that 'self.head'
     # can be None in below else part and giving error
     if self.head is None:
       return None
     else:
       UpperCAmelCase :							List[str]								=				self.head.item
       UpperCAmelCase :							Optional[int]								=				self.head.next
       self.size -= 1
       return item



   def  __magic_name__					(							self							:  List[str]		):
     return self.head is None



   def __str__(							self							:  Union[str, Any]		):
     if self.is_empty():
       return ""
     else:
       UpperCAmelCase :							Any								=				self.head
       UpperCAmelCase :							Any								=				''''''
       UpperCAmelCase :							list[str]								=				[]
       while iterate:
         item_list.append(str(iterate.item		)		)
         UpperCAmelCase :							Any								=				iterate.next

       UpperCAmelCase :							str								=				''' --> '''.join(__A		)

       return item_str





   def __len__(							self							:  Tuple		):
     return self.size








def     a__  (	UpperCAmelCase							:    List[str]       ,				UpperCAmelCase							:    List[Any]    )						->		Optional[int]:
  print('''\nVertex Distance'''    )
  for i in range(UpperCAmelCase    ):
    if dist[i] != float('''inf'''    ):
      print(UpperCAmelCase       ,				'''\t'''       ,				int(dist[i]    )       ,				end='''\t'''    )
    else:
      print(UpperCAmelCase       ,				'''\t'''       ,				'''INF'''       ,				end='''\t'''    )
    print()

def     a__  (	UpperCAmelCase							:    Tuple       ,				UpperCAmelCase							:    Optional[int]       ,				UpperCAmelCase							:    Optional[int]    )						->		Any:
  UpperCAmelCase :							Union[str, Any]								=				float('''inf'''    )
  UpperCAmelCase :							str								=				-1
  for i in range(UpperCAmelCase    ):
    if (not vset[i]) and mdist[i] < min_val:
      UpperCAmelCase :							int								=				i
      UpperCAmelCase :							Union[str, Any]								=				mdist[i]
  return min_ind

def     a__  (	UpperCAmelCase							:    Union[str, Any]       ,				UpperCAmelCase							:    Optional[Any]       ,				UpperCAmelCase							:    str    )						->		Tuple:
  UpperCAmelCase :							str								=				[float('''inf'''    ) for _ in range(UpperCAmelCase    )]
  UpperCAmelCase :							Optional[int]								=				[False for _ in range(UpperCAmelCase    )]
  UpperCAmelCase :							List[Any]								=				0.0

  for _ in range(v - 1    ):
    UpperCAmelCase :							Any								=				min_dist(UpperCAmelCase       ,				UpperCAmelCase       ,				UpperCAmelCase    )
    UpperCAmelCase :							List[Any]								=				True

    for i in range(UpperCAmelCase    ):
      if (
          (not vset[i])
          and graph[u][i] != float('''inf'''    )
          and mdist[u] + graph[u][i] < mdist[i]
      ):
        UpperCAmelCase :							str								=				mdist[u] + graph[u][i]

  print_dist(UpperCAmelCase       ,				UpperCAmelCase    )


if __name__ == "__main__":
     _lowerCamelCase       :     Tuple           =							int(input("Enter number of vertices: ").strip())
     _lowerCamelCase       :     List[str]           =							int(input("Enter number of edges: ").strip())

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

     for i in range(V):
          _lowerCamelCase       :     Union[str, Any]           =							0.0

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

     _lowerCamelCase       :     List[str]           =							int(input("\nEnter shortest path source:").strip())
     dijkstra(graph, V, gsrc)





