class Pair
{
    int vertex;
    int weight;
    Pair(int weight, int vertex)
    {
        this.weight = weight;
        this.vertex = vertex;
    }
}

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int V = points.length;

        // Step-1 Create an adjacency list: each node has (weight, neighbor)
        List<List<int[]>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<>());
        }
        
        // Step-2 build edges
        for(int i=0; i<V; i++) 
        {
            for(int j=i+1; j<V; j++) 
            {
                int weight = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);

                adj.get(i).add(new int[]{weight, j});
                adj.get(j).add(new int[]{weight, i}); // undirected
            }
        }

        // Step-3 Create a visited array
        boolean[] visited = new boolean[V];
    
        // Step-4 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 currentNode = pair.vertex;
            int currentWeight = pair.weight;

            if(visited[currentNode])
                continue;
            
            visited[currentNode] = true;
            sum += currentWeight;

            // traverse neighbour nodes
            for(int[] neighbour : adj.get(currentNode))
            {
                int vertex = neighbour[1];
                int weight = neighbour[0];
                if(visited[vertex] == false)
                {
                    pq.add(new Pair(weight, vertex));
                }
            }
        }
        return sum;
    }
}