def floyd_warshall(n, edge):
    rn = range(n)
    dist = [[inf] * n for i in rn]
    nxt  = [[0]   * n for i in rn]

    for i in rn:
        for j in rn:
            nxt[i][j]=[-1]

    for i in rn:
        dist[i][i] = 0

    for u, v, w in edge:
        dist[u][v] = w
        nxt[u][v]=[v]

    for k in rn:
        for i in rn:
            for j in rn:
                sum_ik_kj = dist[i][k] + dist[k][j]
                if dist[i][j] > sum_ik_kj:
                   dist[i][j] = sum_ik_kj
                   nxt[i][j]=nxt[i][k]

                elif(sum_ik_kj==dist[i][j] and dist[i][j]!=inf and k!=j and k!=i):
                   nxt[i][j].extend(nxt[i][k])

    return nxt

edge = [[0,2,2],[2,3,2],[3,1,1],[1,0,4],[1,2,3],[0,3,4],[3,0,5]]
# Here n is the value of the highest numbered-vertex. In the above graph, n=4
n=4
nxt=floyd_warshall(n,edge)

for i in range(n):
    for j in range(n):
        if(i!=j):
            allPaths=[]
            allPaths=getpath(i,j,next,allPaths)
            print(allPaths)

def getpath(i,j,nxt,allPaths):
    for k in next[i][j]:
        if(k==-1):
            allPaths.extend([i,j])

        elif(k==j):
            allPaths.append(j)

        else:
            paths_I_K=getpath(i,k,next,allPaths)
            paths_K_J=getpath(k,j,next,allPaths)
            for i_k in paths_I_K:
                for k_j in paths_K_J:
                    i_k.pop()
                    allPaths.append(i_k+k_j)
    return allPaths