


'''simple docstring'''

from __future__ import annotations







class 			UpperCAmelCase			:

 def __init__(			self			:						List[str],       a_			:						int       ):





    """simple docstring"""



    UpperCamelCase__			    =    vertices
    UpperCamelCase__			    =    [[0] * vertices for _ in range(a_       )]

 def 		lowercase_    (			self			:						List[Any],       a_			:						list[int]       ):





    """simple docstring"""



    print("Vertex \t Distance from Source"       )
    for vertex in range(self.vertices       ):
       print(a_,       "\t\t",       distances_from_source[vertex]       )

 def 		lowercase_    (			self			:						List[Any],       a_			:						list[int],       a_			:						list[bool]       ):





    """simple docstring"""



    UpperCamelCase__			    =    1e7
    UpperCamelCase__			    =    0

    # Search not nearest vertex not in the shortest path tree
    for vertex in range(self.vertices       ):
       if distances_from_source[vertex] < minimum and visited[vertex] is False:
          UpperCamelCase__			    =    distances_from_source[vertex]
          UpperCamelCase__			    =    vertex
    return min_index

 def 		lowercase_    (			self			:						Optional[int],       a_			:						int       ):





    """simple docstring"""



    UpperCamelCase__			    =    [int(1e7       )] * self.vertices  # distances from the source
    UpperCamelCase__			    =    0
    UpperCamelCase__			    =    [False] * self.vertices

    for _ in range(self.vertices       ):
       UpperCamelCase__			    =    self.minimum_distance(a_,       a_       )
       UpperCamelCase__			    =    True

       # Update dist value of the adjacent vertices
       # of the picked vertex only if the current
       # distance is greater than new distance and
       # the vertex in not in the shortest path tree
       for v in range(self.vertices       ):
          if (
              self.graph[u][v] > 0
              and visited[v] is False
              and distances[v] > distances[u] + self.graph[u][v]
          ):
             UpperCamelCase__			    =    distances[u] + self.graph[u][v]

    self.print_solution(a_       )


if __name__ == "__main__":
       __lowercase:		Dict    						=  Graph(9)
       __lowercase:		List[str]    						=  [
           [0, 4, 0, 0, 0, 0, 0, 8, 0],
           [4, 0, 8, 0, 0, 0, 0, 11, 0],
           [0, 8, 0, 7, 0, 4, 0, 0, 2],
           [0, 0, 7, 0, 9, 14, 0, 0, 0],
           [0, 0, 0, 9, 0, 10, 0, 0, 0],
           [0, 0, 4, 14, 10, 0, 2, 0, 0],
           [0, 0, 0, 0, 0, 2, 0, 1, 6],
           [8, 11, 0, 0, 0, 0, 1, 0, 7],
           [0, 0, 2, 0, 0, 0, 6, 7, 0],
       ]
       graph.dijkstra(0)




"""simple docstring"""







def 	lowerCAmelCase__      (  lowerCamelCase__      )			->				List[str]:
							A    =       [701, 301, 132, 57, 23, 10, 4, 1]
							for gap in gaps:
														for i in range(lowerCamelCase__					,   len(lowerCamelCase__      )      ):
																					A    =       collection[i]
																					A    =       i
																					while j >= gap and collection[j - gap] > insert_value:
																												A    =       collection[j - gap]
																												j -= gap
																					if j != i:
																												A    =       insert_value
							return collection


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

							testmod()
							A     =      input('Enter numbers separated by a comma:\n').strip()
							A     =      [int(item) for item in user_input.split(',')]
							print(shell_sort(unsorted))



