Naive Version

• Find the closest vertex in $Q$ for $O(|V|)$ times: $O(|V|log|V|)$.
• Each edge is inspected at most once throughout the algorithm: $O(|E|)$.
• The time complexity of the whole algorithm is $O(|V|^2 + |E|)$.

With a Priority Queue

• Adding all vertexes to the priority queue: $O(|V| log|V|)$
• Extract min for $|V|$ times: $O(|V| log|V|)$
• Decrease priority for $|E|$ times: $O(|E| log|V|)$
• The time complexity of the whole algorithm is $O((|V| + |E|) log|V|)$