All minimum spanning trees implementation

I don't know if this is the solution, but it's a solution (it's the graph version of a brute force, I would say):

1. Find the MST of the graph using kruskal's or prim's algorithm. This should be O(E log V).
2. Generate all spanning trees. This can be done in O(Elog(V) + V + n) for n = number of spanning trees, as I understand from 2 minutes's worth of google, can possibly be improved.
3. Filter the list generated in step #2 by the tree's weight being equal to the MST's weight. This should be O(n) for n as the number of trees generated in step #2.

Note: Do this lazily! Generating all possible trees and then filtering the results will take O(V^2) memory, and polynomial space requirements are evil - Generate a tree, examine it's weight, if it's an MST add it to a result list, if not - discard it.
Overall time complexity: O(Elog(V) + V + n) for G(V,E) with n spanning trees

Ronald Rivest has a nice implementation in Python, mst.py

You can find an idea in the work of Sorensen and Janssens (2005).

The idea is to generate the STs in the increasing order, and as soon as you get the bigger value of ST stop the enumeration.