dijkstra

inf = float("inf")

def createGraph(n):
    M = []
    for i in range(n):
        M.append([])
        for j in range(n):
            M[i].append(inf)
    return M


def size(G):
    return len(G)


def insert(G, i, j, w):
    G[i][j] = w


def delete(G, i, j):
    G[i][j] = inf


def isEdge(G, i, j):
    return G[i][j] != []


def weight(G, i, j):
    return G[i][j]


def getAdjacents(G, i):
    V = []
    for j in range(len(G)):
        if G[i][j] != inf:
            V.append([j, G[i][j]])
    return V


def minVertex(D, V):
    min = inf
    y = -1
    for i in range(len(D)):
        if (not V[i]) and (D[i] < min):
            y = i
            min = D[i]
    return y


def Dijkstra(G, s):
    n = size(G)

    dist = []
    visited = []

    for i in range(n):
        dist.append(inf)
        visited.append(False)

    dist[s] = 0

    for i in range(n - 1):
        next = minVertex(dist, visited)
        visited[next] = True

        V = getAdjacents(G, next)
        for [z, w] in V:
            d = dist[next] + w
            if dist[z] > d:
                dist[z] = d

    return dist


########################

G = createGraph(6)

insert(G, 0, 1, 2)
insert(G, 0, 5, 9)
insert(G, 1, 3, 8)
insert(G, 1, 2, 6)
insert(G, 1, 5, 5)
insert(G, 2, 3, 1)
insert(G, 4, 3, 3)
insert(G, 4, 2, 7)
insert(G, 5, 4, 3)


D = Dijkstra(G, 0)
print("")
print(D[0])
print(D[1])