The queue can handle everything, as long as you supply it with a compare function and an identity function, so you'd need an edge index as identity and sth that compares two edge descriptors according to their weight (if that's what you want), some functor with a reference to an edge weight map implementing
http://www.sgi.com/tech/stl/StrictWeakOrdering.html would do. I don't have the time to construct an example atm, but this should work.