Summary: Given a graph $G$ and a positive integer $k$, we want to find $k$ spanning trees on $G$, not necessarily disjoint, of minimum total weight, such that the weight of each edge is subject to a penalty function if it belongs to more than one tree. We present a polynomial time algorithm for this problem; the algorithm’s complexity is quadratic in $k$. We also present two heuristics with complexity linear in $k$. In an experimental study we show that these heuristics are much faster than the exact algorithm also in practice, and that their solutions are around 1\% of optimal for small values of $k$ and much better for large $k$.