import math
import copy


def floyd(edgedict,n):
    """
    O(n^3) time, O(n^2) space, Floyd all pairs shortest path.
    """
    # initialize
    d = [[math.inf for i in range(n)] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if (i,j) in edgedict: d[i][j] = edgedict[(i,j)]
    # dynamic programming
    for k in range(n):
        dist = copy.deepcopy(d)
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(d[i][j], d[i][k] + d[k][j])
        d = dist
    
    return d