



import math







def 							A     (						__UpperCAmelCase      )			->			str:



						'''simple docstring'''






						if number == 0:
												UpperCAmelCase_					=	'''Zero'''
												return words
						else:
												UpperCAmelCase_					=	math.logaa(__UpperCAmelCase      )
												UpperCAmelCase_					=	digits + 1
												UpperCAmelCase_					=	{}
												UpperCAmelCase_					=	''''''
												UpperCAmelCase_					=	'''One'''
												UpperCAmelCase_					=	'''Two'''
												UpperCAmelCase_					=	'''Three'''
												UpperCAmelCase_					=	'''Four'''
												UpperCAmelCase_					=	'''Five'''
												UpperCAmelCase_					=	'''Six'''
												UpperCAmelCase_					=	'''Seven'''
												UpperCAmelCase_					=	'''Eight'''
												UpperCAmelCase_					=	'''Nine'''

												UpperCAmelCase_					=	{}
												UpperCAmelCase_					=	''''''
												UpperCAmelCase_					=	'''Twenty'''
												UpperCAmelCase_					=	'''Thirty'''
												UpperCAmelCase_					=	'''Forty'''
												UpperCAmelCase_					=	'''Fifty'''
												UpperCAmelCase_					=	'''Sixty'''
												UpperCAmelCase_					=	'''Seventy'''
												UpperCAmelCase_					=	'''Eighty'''
												UpperCAmelCase_					=	'''Ninety'''

												UpperCAmelCase_					=	{}
												UpperCAmelCase_					=	'''Ten'''
												UpperCAmelCase_					=	'''Eleven'''
												UpperCAmelCase_					=	'''Twelve'''
												UpperCAmelCase_					=	'''Thirteen'''
												UpperCAmelCase_					=	'''Fourteen'''
												UpperCAmelCase_					=	'''Fifteen'''
												UpperCAmelCase_					=	'''Sixteen'''
												UpperCAmelCase_					=	'''Seventeen'''
												UpperCAmelCase_					=	'''Eighteen'''
												UpperCAmelCase_					=	'''Nineteen'''

												UpperCAmelCase_					=	{}
												UpperCAmelCase_					=	'''Hundred,'''
												UpperCAmelCase_					=	'''Thousand,'''
												UpperCAmelCase_					=	'''Lakh,'''
												UpperCAmelCase_					=	'''Crore,'''

												UpperCAmelCase_					=	number
												UpperCAmelCase_					=	''''''
												UpperCAmelCase_					=	0
												UpperCAmelCase_					=	int(__UpperCAmelCase      )
												while counter < digits:
																		UpperCAmelCase_					=	temp_num % 10
																		if counter % 2 == 0:
																								UpperCAmelCase_					=	''''''
																								if counter in placevalue and current != 0:
																														UpperCAmelCase_					=	placevalue[counter]
																								if counter == 2:
																														UpperCAmelCase_					=	singles[current] + addition + words
																								elif counter == 0:
																														if ((temp_num % 100) // 10) == 1:
																																				UpperCAmelCase_					=	teens[current] + addition + words
																																				UpperCAmelCase_					=	temp_num // 10
																																				counter += 1
																														else:
																																				UpperCAmelCase_					=	singles[current] + addition + words

																								else:
																														UpperCAmelCase_					=	doubles[current] + addition + words

																		else:
																								if counter == 1:
																														if current == 1:
																																				UpperCAmelCase_					=	teens[number % 10] + words
																														else:
																																				UpperCAmelCase_					=	''''''
																																				if counter in placevalue:
																																										UpperCAmelCase_					=	placevalue[counter]
																																				UpperCAmelCase_					=	doubles[current] + addition + words
																								else:
																														UpperCAmelCase_					=	''''''
																														if counter in placevalue:
																																				if current == 0 and ((temp_num % 100) // 10) == 0:
																																										UpperCAmelCase_					=	''''''
																																				else:
																																										UpperCAmelCase_					=	placevalue[counter]
																														if ((temp_num % 100) // 10) == 1:
																																				UpperCAmelCase_					=	teens[current] + addition + words
																																				UpperCAmelCase_					=	temp_num // 10
																																				counter += 1
																														else:
																																				UpperCAmelCase_					=	singles[current] + addition + words
																		counter += 1
																		UpperCAmelCase_					=	temp_num // 10
						return words


if __name__ == "__main__":
							import doctest

							doctest.testmod()










def 							A     (						__UpperCAmelCase				,   __UpperCAmelCase      )			->			int:



						'''simple docstring'''






						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				,   __UpperCAmelCase				,   __UpperCAmelCase      )			->			str:



						'''simple docstring'''






						UpperCAmelCase_					=	float('''inf'''      )
						UpperCAmelCase_					=	-1
						for i in range(__UpperCAmelCase      ):
												if (not vset[i]) and mdist[i] < min_val:
																		UpperCAmelCase_					=	i
																		UpperCAmelCase_					=	mdist[i]
						return min_ind







def 							A     (						__UpperCAmelCase				,   __UpperCAmelCase				,   __UpperCAmelCase      )			->			Optional[Any]:



						'''simple docstring'''






						UpperCAmelCase_					=	[float('''inf'''      ) for _ in range(__UpperCAmelCase      )]
						UpperCAmelCase_					=	[False for _ in range(__UpperCAmelCase      )]
						UpperCAmelCase_					=	0.0

						for _ in range(v - 1      ):
												UpperCAmelCase_					=	min_dist(__UpperCAmelCase				,   __UpperCAmelCase				,   __UpperCAmelCase      )
												UpperCAmelCase_					=	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_					=	mdist[u] + graph[u][i]

						print_dist(__UpperCAmelCase				,   __UpperCAmelCase      )


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

							UpperCamelCase_      			=  [[float("inf") for i in range(V)] for j in range(V)]

							for i in range(V):
														UpperCamelCase_      			=  0.0

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

							UpperCamelCase_      			=  int(input("\nEnter shortest path source:").strip())
							dijkstra(graph, V, gsrc)





