INF = float('inf')

def floyd_warshall(graph):
    n = len(graph)
    d = [row[:] for row in graph]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

graph = [
    [0,   1,   6, INF],
    [INF, 0,   4,   1],
    [INF, INF, 0, INF],
    [INF, INF, 1,   0]
]

for row in floyd_warshall(graph):
    print(row)

def floyd_warshall_with_path(graph, nxt):
    n = len(graph)
    d = [row[:] for row in graph]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    nxt[i][j] = nxt[i][k]
    return d, nxt

def get_path(u, v, d, nxt):
    if d[u][v] == INF:
        return None                 
    path = [u]
    while u != v:
        u = nxt[u][v]
        path.append(u)
    return path