'''simple docstring'''


def    _lowerCamelCase       ( lowerCamelCase_   :				List[str]      ,	lowerCamelCase_   :				Union[str, Any]  ):



     """simple docstring"""





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


def    _lowerCamelCase       ( lowerCamelCase_   :				Union[str, Any]      ,	lowerCamelCase_   :				int      ,	lowerCamelCase_   :				str  ):



     """simple docstring"""





     UpperCAmelCase_				:  Dict  = float('inf'  )
     UpperCAmelCase_				:  Tuple  = -1
     for i in range(lowerCamelCase_  ):
          if (not vset[i]) and mdist[i] < min_val:
               UpperCAmelCase_				:  int  = i
               UpperCAmelCase_				:  Optional[Any]  = mdist[i]
     return min_ind


def    _lowerCamelCase       ( lowerCamelCase_   :				int      ,	lowerCamelCase_   :				Optional[Any]      ,	lowerCamelCase_   :				Any  ):



     """simple docstring"""





     UpperCAmelCase_				:  str  = [float('inf'  ) for _ in range(lowerCamelCase_  )]
     UpperCAmelCase_				:  Union[str, Any]  = [False for _ in range(lowerCamelCase_  )]
     UpperCAmelCase_				:  Optional[Any]  = 0.0

     for _ in range(v - 1  ):
          UpperCAmelCase_				:  Tuple  = min_dist(lowerCamelCase_      ,	lowerCamelCase_      ,	lowerCamelCase_  )
          UpperCAmelCase_				:  Dict  = True

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

     print_dist(lowerCamelCase_      ,	lowerCamelCase_  )


if __name__ == "__main__":
 snake_case__	:     Union[str, Any]      =    int(input('''Enter number of vertices: ''').strip())
 snake_case__	:     Any      =    int(input('''Enter number of edges: ''').strip())

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

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

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

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











def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					if right <= left:
										return
					lowercase						   =       lowercase						   =       left
					lowercase						   =       right
					lowercase						   =       sorting[left]
					while i <= b:
										if sorting[i] < pivot:
															lowercase   ,      lowercase						   =       sorting[i], sorting[a]
															a += 1
															i += 1
										elif sorting[i] > pivot:
															lowercase   ,      lowercase						   =       sorting[i], sorting[b]
															b -= 1
										else:
															i += 1
					quick_sort_apartition(_UpperCAmelCase       ,			_UpperCAmelCase       ,			a - 1				)
					quick_sort_apartition(_UpperCAmelCase       ,			b + 1       ,			_UpperCAmelCase				)





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					if left < right:
										lowercase						   =       lomuto_partition(_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				)
										quick_sort_lomuto_partition(_UpperCAmelCase       ,			_UpperCAmelCase       ,			pivot_index - 1				)
										quick_sort_lomuto_partition(_UpperCAmelCase       ,			pivot_index + 1       ,			_UpperCAmelCase				)





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					lowercase						   =       sorting[right]
					lowercase						   =       left
					for i in range(_UpperCAmelCase       ,			_UpperCAmelCase				):
										if sorting[i] < pivot:
															lowercase   ,      lowercase						   =       sorting[i], sorting[store_index]
															store_index += 1
					lowercase   ,      lowercase						   =       sorting[store_index], sorting[right]
					return store_index





def 		__snake_case						(    _UpperCAmelCase				):
					"""simple docstring"""






					if len(_UpperCAmelCase				) <= 1:
										return sorting
					return (
					    three_way_radix_quicksort([i for i in sorting if i < sorting[0]]				)
					    + [i for i in sorting if i == sorting[0]]
					    + three_way_radix_quicksort([i for i in sorting if i > sorting[0]]				)
					)


if __name__ == "__main__":
		import doctest

		doctest.testmod(verbose=True)

		__magic_name__       =     input('''Enter numbers separated by a comma:\n''').strip()
		__magic_name__       =     [int(item) for item in user_input.split(''',''')]
		quick_sort_apartition(unsorted, 0, len(unsorted) - 1)
		print(unsorted)






