



class 			_lowercase							:





	"""simple docstring"""




	def __init__(self	, lowerCamelCase_	):
						"""simple docstring"""

						a        =     data
						a        =     None
						a        =     None




	def __str__(self	):
						"""simple docstring"""

						return F'''{self.data}'''




class 			_lowercase							:





	"""simple docstring"""




	def __init__(self	):
						"""simple docstring"""

						a        =     None
						a        =     None




	def __iter__(self	):
						"""simple docstring"""

						a        =     self.head
						while node:
											yield node.data
											a        =     node.next




	def __str__(self	):
						"""simple docstring"""

						return "->".join([str(lowerCamelCase_	) for item in self]	)




	def __len__(self	):
						"""simple docstring"""

						return sum(1 for _ in self	)




	def   UpperCamelCase_ (self	, lowerCamelCase_	):
						"""simple docstring"""

						self.insert_at_nth(0	, lowerCamelCase_	)




	def   UpperCamelCase_ (self	, lowerCamelCase_	):
						"""simple docstring"""

						self.insert_at_nth(len(self	)	, lowerCamelCase_	)




	def   UpperCamelCase_ (self	, lowerCamelCase_	, lowerCamelCase_	):
						"""simple docstring"""

						a        =     len(self	)

						if not 0 <= index <= length:
											raise IndexError("list index out of range"	)
						a        =     Node(lowerCamelCase_	)
						if self.head is None:
											a        =     a        =     new_node
						elif index == 0:
											a        =     new_node
											a        =     self.head
											a        =     new_node
						elif index == length:
											a        =     new_node
											a        =     self.tail
											a        =     new_node
						else:
											a        =     self.head
											for _ in range(0	, lowerCamelCase_	):
																a        =     temp.next
											a        =     new_node
											a        =     temp.previous
											a        =     temp
											a        =     new_node




	def   UpperCamelCase_ (self	):
						"""simple docstring"""

						return self.delete_at_nth(0	)




	def   UpperCamelCase_ (self	):
						"""simple docstring"""

						return self.delete_at_nth(len(self	) - 1	)




	def   UpperCamelCase_ (self	, lowerCamelCase_	):
						"""simple docstring"""

						a        =     len(self	)

						if not 0 <= index <= length - 1:
											raise IndexError("list index out of range"	)
						a        =     self.head  # default first node
						if length == 1:
											a        =     a        =     None
						elif index == 0:
											a        =     self.head.next
											a        =     None
						elif index == length - 1:
											a        =     self.tail
											a        =     self.tail.previous
											a        =     None
						else:
											a        =     self.head
											for _ in range(0	, lowerCamelCase_	):
																a        =     temp.next
											a        =     temp
											a        =     temp.previous
											a        =     temp.next
						return delete_node.data




	def   UpperCamelCase_ (self	, lowerCamelCase_	):
						"""simple docstring"""

						a        =     self.head

						while current.data != data:  # Find the position to delete
											if current.next:
																a        =     current.next
											else:  # We have reached the end an no value matches
																raise ValueError("No data matching given value"	)

						if current == self.head:
											self.delete_head()

						elif current == self.tail:
											self.delete_tail()

						else:  # Before: 1 <--> 2(current) <--> 3
											a        =     current.next  # 1 --> 3
											a        =     current.previous  # 1 <--> 3
						return data




	def   UpperCamelCase_ (self	):
						"""simple docstring"""

						return len(self	) == 0






def 					a(   )	-> None:
					"""simple docstring"""





					a        =     DoublyLinkedList()
					assert linked_list.is_empty() is True
					assert str(A ) == ""

					try:
										linked_list.delete_head()
										raise AssertionError  # This should not happen.
					except IndexError:
										assert True  # This should happen.

					try:
										linked_list.delete_tail()
										raise AssertionError  # This should not happen.
					except IndexError:
										assert True  # This should happen.

					for i in range(10 ):
										assert len(A ) == i
										linked_list.insert_at_nth(A				,  i + 1 )
					assert str(A ) == "->".join(str(A ) for i in range(1				,  11 ) )

					linked_list.insert_at_head(0 )
					linked_list.insert_at_tail(11 )
					assert str(A ) == "->".join(str(A ) for i in range(0				,  12 ) )

					assert linked_list.delete_head() == 0
					assert linked_list.delete_at_nth(9 ) == 10
					assert linked_list.delete_tail() == 11
					assert len(A ) == 9
					assert str(A ) == "->".join(str(A ) for i in range(1				,  10 ) )


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

				testmod()





def 					a(   A :					Optional[Any]				,  A :					List[str] )	-> List[Any]:
					"""simple docstring"""





					print("\nVertex Distance" )
					for i in range(A ):
										if dist[i] != float("inf" ):
															print(A				,  "\t"				,  int(dist[i] )				,  end="\t" )
										else:
															print(A				,  "\t"				,  "INF"				,  end="\t" )
										print()






def 					a(   A :					str				,  A :					int				,  A :					int )	-> Optional[int]:
					"""simple docstring"""





					a        =     float("inf" )
					a        =     -1
					for i in range(A ):
										if (not vset[i]) and mdist[i] < min_val:
															a        =     i
															a        =     mdist[i]
					return min_ind






def 					a(   A :					List[str]				,  A :					Union[str, Any]				,  A :					Dict )	-> Tuple:
					"""simple docstring"""





					a        =     [float("inf" ) for _ in range(A )]
					a        =     [False for _ in range(A )]
					a        =     0.0

					for _ in range(v - 1 ):
										a        =     min_dist(A				,  A				,  A )
										a        =     True

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

					print_dist(A				,  A )


if __name__ == "__main__":
				_lowercase:				Any       =	int(input("Enter number of vertices: ").strip())
				_lowercase:				Optional[Any]       =	int(input("Enter number of edges: ").strip())

				_lowercase:				List[str]       =	[[float("inf") for i in range(V)] for j in range(V)]

				for i in range(V):
								_lowercase:				List[Any]       =	0.0

				for i in range(E):
								print("\nEdge ", i + 1)
								_lowercase:				Tuple       =	int(input("Enter source:").strip())
								_lowercase:				Tuple       =	int(input("Enter destination:").strip())
								_lowercase:				int       =	float(input("Enter weight:").strip())
								_lowercase:				str       =	weight

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