Appropriate container for prim's algorithm

I have a question.
I'm working on an implementation on Prim's algorithm currently, and I need an appropriate container.
Since I need to find the lowest cost edge, I wanted a container that could effectively sort the data to keep them in a sorted order, so that I could take the first edge, check if it's one I can use, and if not, pick the next lowest weight, and so on.

I have thought about priority queues. Only, they lack iterators. That means I would have to pop the front, check it, then push it if it doesn't fit what I need. And then it appear in the front again.

A binary heap wouldn't necessarily keep the items in sorted order, nor do I think they have iterators, so that wouldn't do either. Or if it did, it would probably be a little more complicated.

Another option, I suppose, would be some queue I could sort of a linked list to which I apply mergesort, since from my experiements, it's pretty fast on sorted data.

Those are my thoughts.
Now I want to know if anyone else has any ideas or thoughts.
Thanks.

wikipedia is quite good for this:
Prim's algorithm - Wikipedia, the free encyclopedia

For learning how the algorithm works, yes, but not for implementing it.

Did you read the link I sent? It goes directly to time complexity per data structure. That's what you want, isn't it?

Yes, I saw that. But if that was enough, I wouldn't be asking.
I have been to Wikipedia, oh I don't know how many times, looking at this algorithm and others.

Well, I don't know if how I always did it is optimal... But I'd store all edges per vertex in a vector. Then pick a random vertex and insert all edges in a set, sorted by length. Then I'd pick the shortest edge by selecting the first one in the set that doesn't have a vector in the spanning tree on both ends (simply a vector of bools per vertex, set to false to begin with). Then I'd insert all edges from the new vertex into the set and continue like that.

In the programming contests this solution was always fast enough, though I doubt it's optimal.

I did solve this some two days ago. Probably not optimal.
Still, I will be going back to some work requiring the use of a graph and finding the shortest path between two nodes, so I'll come back to this algorithm a little later, and I'll look at optimizing it a little more.