# Prim's algorithm for finding the minimum spanning tree

So I was coding Prim's algorithm for practice and this is what I wrote. It works for finding the weight of the minimum spanning tree (MST) but I'm wondering if the loop I am doing to add the the edges in the frontier to the minheap is optimal.

import heapq
from collections import defaultdict
g = defaultdict(list)
weight = 0
connected = set([])
pq = []

#n is the number of nodes m is the number of edges
n, m = [int(x) for x in raw_input().split(" ")]
#create adjacency list from inputs of the form "vertex1 vertex2 weight"
for _ in xrange(m):
a, b, w = [int(x) for x in raw_input().split(" ")]
g[a].append((w, b))
g[b].append((w, a))

start = int(raw_input())
for tup in g[start]:
heapq.heappush(pq, tup)
while pq:
w, b = heapq.heappop(pq)
if b not in connected:
weight += w
#by how much does this loop affect the run time of Prims?
for tup in g[b]:
heapq.heappush(pq, tup)

print weight


Your while pq loop continues to run long after it needs to. Consider breaking at the bottom of the loop if len(connected) == n, assuming your graph is one component.
#n is the number of nodes m is the number of edges

The same applies to g, pq, a.........etc.etc