
n = 11 # vertices number
matrix = [
    [0,3,4,5,99,99,99,99,99,99,99],
    [99,0,99,99,3,1,4,99,99,99,99],
    [99,99,0,99,1,4,1,99,99,99,99],
    [99,99,99,0,1,1,5,99,99,99,99],
    [99,99,99,99,0,99,99,2,3,4,99],
    [99,99,99,99,99,0,99,1,2,3,99],
    [99,99,99,99,99,99,0,1,2,3,99],
    [99,99,99,99,99,99,99,0,99,99,5],
    [99,99,99,99,99,99,99,99,0,99,1],
    [99,99,99,99,99,99,99,99,99,0,4],
    [99,99,99,99,99,99,99,99,99,99,99]]

# v records access information of each node 
v = [0]*n 
# dis is the distance between start node and other nodes
dis = matrix[0].copy()

# start
v[0] = 1
dis[0] = 99

# loop 
for _ in range(n):
    # find the adjacent and nearest node
    k = 0
    for j in range(n):
        if v[j] == 0 and dis[j] < dis[k]:
            k = j
	# this node is accessed 
    v[k] = 1

    # relaxation
    for j in range(n):
        if v[j] == 0 and dis[k] + matrix[k][j] < dis[j]:
            dis[j] = dis[k] + matrix[k][j]

print(dis)