






'''simple docstring'''


def 						__magic_name__(			_A    ,   _A       ):
						'''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 						__magic_name__(			_A    ,   _A    ,   _A       ):
						'''simple docstring'''





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







def 						__magic_name__(			_A    ,   _A    ,   _A       ):
						'''simple docstring'''





						UpperCamelCase__       =			[float("""inf"""       ) for _ in range(_A       )]
						UpperCamelCase__       =			[False for _ in range(_A       )]
						UpperCamelCase__       =			0.0

						for _ in range(v - 1       ):
												UpperCamelCase__       =			min_dist(_A    ,   _A    ,   _A       )
												UpperCamelCase__       =			True

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

						print_dist(_A    ,   _A       )


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

					lowerCamelCase_					:			Tuple     						=				[[float('''inf''') for i in range(V)] for j in range(V)]

					for i in range(V):
										lowerCamelCase_					:			Any     						=				0.0

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

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








'''simple docstring'''


def 						__magic_name__(			_A       ):
						'''simple docstring'''





						UpperCamelCase__       =			len(_A       )

						# Set the gap value to be decreased by a factor of 1.3
						# after each iteration
						UpperCamelCase__       =			1.3

						# Continue sorting until the gap is 1
						while gap > 1:
												# Decrease the gap value
												UpperCamelCase__       =			int(gap / shrink       )

												# Sort the elements using insertion sort
												for i in range(_A    ,   len(_A       )       ):
																		UpperCamelCase__       =			collection[i]
																		UpperCamelCase__       =			i
																		while j >= gap and collection[j - gap] > temp:
																								UpperCamelCase__       =			collection[j - gap]
																								j -= gap
																		UpperCamelCase__       =			temp

						return collection


if __name__ == "__main__":
					import doctest

					doctest.testmod()
