def enumerate_directed_spanning_trees(A, root, root_weight):
    """
    Enumerate all spanning trees in A with an edge coming from the root,
    given a root_weight.
    Spanning trees are given in the form of (i, j, w) indicating a an edge
    from i to j with weight w.
    Weights are additive.
    """
    n = len(A)

    def enum_dst(cost, included, rest, excluded):
        if len(included) == n:
            return [(rest, cost)]
        dsts = []
        new_excluded = list(excluded)
        for i in included:
            for j in range(n):
                cost_ij = A[i, j]
                if j not in included and (i, j) not in excluded and cost_ij:
                    new_excluded += [(i, j)]
                    dsts += enum_dst(cost + cost_ij, included + [j],
                                     rest + [(i, j, cost_ij)], new_excluded)
        return dsts
    return enum_dst(root_weight, [root], [], [])