Minimum Spanning Trees(Prims Algorithm)

#spanning Tree: For N nodes there should be N-1 edges and all the nodes must reach to each other.There can be multiple spanning tree for the same graph.
#Minimum spanning Tree: out of all the spanning tree, MST is the one which has the minimum sum of the weights of the edges.
"""
Intuition for Prim's Algorithm (Minimum Spanning Tree)

Step 1: Identify the Problem Type
---------------------------------
A Minimum Spanning Tree (MST) is a subset of edges that connects all
vertices in a graph without cycles and with the minimum total weight.
Since we want to build this tree 'greedily' by always picking the
next cheapest available edge that connects a new node, we use
Prim's Algorithm.

Step 2: Key Data Structures
---------------------------
1. Priority Queue (Min-Heap): Stores (weight, node, parent). It helps
   us always pick the edge with the smallest weight available.
2. Visited Array: Keeps track of nodes already included in the MST
   to prevent cycles.
3. Sum: To store the total weight of the MST.
4. MST List: (Optional) To store the actual edges (u, v) that form the tree.

Step 3: Initial Configuration
-----------------------------
- Start with any node (usually node 0).
- Push (0, 0, -1) into the Priority Queue: (weight=0, node=0, parent=-1).
- Visited array is initially all 0s.

Step 4: The Greedy BFS-like Loop
--------------------------------
While the Priority Queue is not empty:
1. Extract the element with the minimum weight from the Min-Heap.
2. Check if the node is already visited:
   - If YES: Ignore it (it's already part of the MST via a cheaper edge).
   - If NO: Mark it as VISITED. This node is now officially in our MST.

Step 5: Adding to Results
-------------------------
- Add the edge weight to our running 'Sum'.
- If parent != -1, add the edge (parent, node) to our MST List.

Step 6: Exploring Neighbors
---------------------------
For the current node, look at all its adjacent neighbors:
- If a neighbor is NOT visited:
  - Push (edge_weight, neighbor_node, current_node) into the Priority Queue.
- Note: We don't mark neighbors as visited here! We only mark them
  visited when they are 'popped' from the Priority Queue. This
  allows a later, cheaper edge to potentially 'overtake' a more
  expensive one.

Step 7: Complexity
------------------
- Time: O(E * log E) or O(E * log V) - Each edge is pushed/popped
  from the Priority Queue.
- Space: O(V + E) - For the adjacency list, visited array, and
  Priority Queue.
"""

from heapq import heappush, heappop
from collections import defaultdict
class Solution:
    def spanningTree(self, v, edges):
        adj=defaultdict(list)
        for a,b,c in edges:
            adj[a].append((b,c))
            adj[b].append((a,c))
        need=v #because starting node also got included with 0 weight so v
        mst=0
        heap=[]
        heappush(heap,(0,0)) #(cost,node)
        visited=[False]*v
        while heap and need>0:
            cost,node=heappop(heap)
            if visited[node]==True:
                continue
            mst+=cost
            visited[node]=True
            need-=1
            for neigh,w in adj[node]:
                if visited[neigh]==False:
                    heappush(heap,(w,neigh))
        return mst