edge = [[0,1,2],[0,2,5],[1,2,4],[1,3,6],[1,4,10],[2,3,2],[3,5,1],[4,5,3],[4,6,5],[5,6,9],
       [1,0,2],[2,0,5],[2,1,4],[3,1,6],[4,1,10],[3,2,2],[5,3,1],[5,4,3],[6,4,5],[6,5,9]]

def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    while True:
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
    return d

print shortest_path(edge,7,0)[6]

edge = [[0,1,2],[0,2,5],[1,2,4],[1,3,6],[1,4,10],[2,3,2],[3,5,1],[4,5,3],[4,6,5],[5,6,9],
       [1,0,2],[2,0,5],[2,1,4],[3,1,6],[4,1,10],[3,2,2],[5,3,1],[5,4,3],[6,4,5],[6,5,9]]

def dijkstra(edge,num_v,start):
    inf = float("inf")
    cost = [[inf for i in range(num_v)] for j in range(num_v)]
    for e in edge: cost[e[0]][e[1]] = e[2]
    used = [False for i in range(num_v)]
    d = [inf for j in range(num_v)]

    d[start] = 0;
    while True:
        v = -1
        for u in range(num_v):
            if (not used[u]) and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1: break
        used[v] = True
        for x in range(num_v):
            d[x] = d[x] if d[x] < d[v] + cost[v][x] else d[v] + cost[v][x]
        print d
    return d[num_v-1]

print dijkstra(edge,7,0)