def paint_houses(n, m, cost):
    """ Paint a list of N houses and M colors, each combination has cost,
    minimize the total cost without color in row.

    Args
        n - number of houses
        m - number of colors
        cost - cost matrix of each combination. Format {color1: {color2: cost}}

    Returns:
        (min_cost, colors), min_cost - the total min cost of the coloring.
                            colors - the order of the coloring.
    """
    def get_cost(i, j):
        if i in cost:
            if j in cost[i]:
                return cost[i][j]
        return 0

    # Recursion:
    # A[i][j] = min value obtained with i houses given the last color is j
    # A[i][j] = min(A[i-1][k] + cost(k, j)), k != j, i=0..n, j=0..m
    #            k

    # Initialize.
    A = [[0] * m for _ in range(n)]
    B = [[None] * m for _ in range(n)]

    # Compute min cost.
    for i in range(1, n):
        for j in range(0, m):
            min_k = float('inf')
            min_partial_cost = float('inf')
            for k in range(0, m):
                if k == j:
                    continue
                partial_cost = A[i-1][k] + get_cost(k, j)
                if partial_cost < min_partial_cost:
                    min_partial_cost = partial_cost
                    min_k = k
            A[i][j] = min_partial_cost
            B[i][j] = min_k

    (min_k, min_cost) = min(enumerate([A[n-1][k] for k in range(0, m)]), key=lambda t: t[1])

    # Compute the color ordering that yields min cost.
    colors = []
    i = n-1 # Count houses.
    while i >= 0:
        colors.append(min_k)
        min_k = B[i][min_k]
        i -= 1
    colors.reverse()

    return (min_cost, colors)