---
# System prepended metadata

title: Prim's MST

---

# Prim's MST

```python
import heapq
from collections import defaultdict

class Solution:
    
    def minimumCost(self, N: int, connections: List[List[int]]) -> int:
        
        graph = defaultdict(list)

        for u,v,w in connections:
            graph[u].append([w,v])
            graph[v].append([w,u])
        
        visited = {k:False for k in graph.keys()}
        
        s = connections[0][0]
        q = [[0, s]]

        cost = 0
                
        while q:
            w1,u = heapq.heappop(q)
            
            if not visited[u]:
                cost += w1
                visited[u] = True
                for w2,v in graph[u]:
                    if not visited[v]:
                        heapq.heappush(q,(w2,v))

        if sum(visited.values()) == N:
            return cost
        else:
            return -1
```