class Pair {
    int vertex;
    int weight;
 
    Pair(int weight, int vertex) 
    {
        this.vertex = vertex;
        this.weight = weight;
    }
}
 
class Solution {
    /**
     * Start from any node and keep adding the minimum weight edge that connects a visited node to an unvisited node.
     * Step 1: Build Adjacency List
     * Step 2: Use a Min Heap (Priority Queue) 
     *      -- This ensures we always pick the minimum weight edge
     *      -- Each entry in PQ = (weight, node)
     * Step 3: Start from Node 0, Start with node 0 and Weight = 0 (no cost to start)
     * Step 4: Maintain Visited Array and sum as 0
     * Step 5: Main Loop (Core of Prim’s)
     *      -- Extract minimum edge
     *      -- Always picks the smallest weight edge available
     *      -- Skip if already visited, Avoids revisiting nodes (cycle prevention)
     *      -- Include this edge in MST
     *      -- Add its weight to total cost
     *      -- Explore neighbors and Push all adjacent edges into PQ, Only if neighbor is not visited
     * Step 6: Return sum of all edges
     */
    public int spanningTree(int V, int[][] edges) {
        // Step-1 Create an adjacency list
        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<Pair>());
        }
 
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
 
            adj.get(u).add(new Pair(w, v));
            adj.get(v).add(new Pair(w, u)); // undirected
        }
 
        // Step-2 Create a visited array
        boolean[] visited = new boolean[V];
 
        // Step-3 Define a min-heap <weight, node> 
        PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Integer.compare(x.weight, y.weight));
        pq.offer(new Pair(0, 0));
 
        int sum = 0;
        while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int weight = pair.weight;
            int currentNode = pair.vertex;
 
            if(visited[currentNode])
                continue;
 
            visited[currentNode] = true;
            sum += weight;
 
            // traverse the neighbour nodes
            for(Pair neighbour : adj.get(currentNode))
            {
                if(visited[neighbour.vertex] == false)
                {
                    pq.offer(new Pair(neighbour.weight, neighbour.vertex));
                }
            }
        }
        return sum;
    }
}