N     = 6
inf   = float("inf")
dist  = [[inf]*N for v in range(N)]
f     = [[None]*N for v in range(N)]
nocost= 0.01
edges = [
    (0, 4, nocost),
    (0, 3, nocost),
    (1, 4, 1),
    (1, 3, nocost),
    (1, 2, nocost),
    (2, 0, nocost),
    (2, 5, nocost),
    (4, 0, nocost),
    (5, 2, nocost),
    (5, 3, nocost)]

#self-edges
edges += [(v, v, nocost) for v in range(N)]

for first, second, weight in edges:
    dist[first][second] = weight
    f[first][second] = second

for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][j] >= dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                if dist[i][j] < inf:
                    #prevent circular routes for unreachable vertices
                    f[i][j]    = f[i][k]

for l in dist:
    print(l)
for l in f:
    print(l)