def kruskal(edges, V):

        # Sort edges by weight
        edges.sort(key=lambda x: x[2])

        # Union Find data structure
        parent = [i for i in range(V)]
        rank = [0] * V

        def find(u):
            if parent[u] != u:
                parent[u] = find(parent[u])
            return parent[u]

        def union(u, v):
            pu, pv = find(u), find(v)
            if pu == pv:
                return False
            if rank[pu] < rank[pv]:
                parent[pu] = pv
            else:
                parent[pv] = pu
                if rank[pu] == rank[pv]:
                    rank[pu] += 1
            return True

        mst = []
        total_weight = 0
        for u, v, w in edges:
            if union(u, v):
                mst.append((u, v, w))
                total_weight += w

        return mst, total_weight

    def prim(graph, start):
        """
        graph: adjacency list {node: [(neighbor, weight), ...]}
        start: starting vertex
        """

        visited = set()
        min_heap = [(0, start)]
        total_weight = 0
        mst = []

        while min_heap and len(visited) < len(graph):
            w, u = heapq.heappop(min_heap)
            if u in visited:
                continue
            visited.add(u)
            total_weight += w

            for v, weight in graph[u]:
                if v not in visited:
                    heapq.heappush(min_heap, (weight, v))
                    mst.append((u, v, weight))

        return mst, total_weight

class UnionFind:

    # Defining Our Union Find Class

    def __init__(self, n):

        # Each node starts as its own parent (separate component)
        # sc: O(V)
        self.parent = list(range(n))

        # Rank approximates tree depth (used for balancing)
        # sc: O(V)
        self.rank = [0] * n

    # Find root representative of component with path compression
    # tc: O(α(V))
    def find(self, x):

        # if root of node is not self, recurse upwards
        if self.parent[x] != x:

            # Path Compression:
            # Flattens tree for faster future lookups
            # tc: O(1) amortized
            self.parent[x] = self.find(self.parent[x])

        # return parent of original after path compression
        return self.parent[x]


    # Union by rank: attach tree with less height under the taller one
    # based on union upper bound on height
    # tc: O(α(V))
    def union(self, x, y):

        # Nodes belong to same component: adding edge would create a cycle
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return False

        # Union by Rank:
        # Attach smaller tree under larger tree
        if self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        else:

            # Only increase rank of trees are of same rank
            self.parent[yr] = xr
            self.rank[xr] += 1

            # Successful Union
        return True

class Solution:

    # Defining Our Kruskal's Algorithm:


    def minCostConnectPoints(self, points: list[list[int]]) -> int:
        
        # Kruskal's Algorithm (Minimum Spanning Tree):
        # 1. Build all possible edges
        # 2. Sort edges by smallest weight
        # 3. Add edges greedily if they do NOT form a cycle,
        #    with cycle detection via Union Find, successful or failed Union operations

        # Cycle detection is handled efficiently using Union Find

        n = len(points)
        edges = []


        # Build All Edges (Manhattan Distance):
        # We are calculating the distance between nodes based on the coordinates,
        # and then using that as the edge weight.
        # tc: O(n^2)
        # sc: O(n^2)
        for i in range(n):
            for j in range(i + 1, n):

                # two points we are getting distance between
                x1, y1 = points[i]
                x2, y2 = points[j]

                # Manhattan Distance = |x1 - x2| + |y1 - y2|
                # where point 1 = (x1, y1)
                #       point 2 = (x2, y2)
                cost = abs(x1 - x2) + abs(y1 - y2)

                # Add edge weight to edge map
                edges.append((cost, i, j))

        # Sort edges by cost:
        # tc: O(E log E)
        edges.sort()

        # Kruskal Add Edges Greedily:
        # Add the smallest edge first and check if it does NOT form a cycle via
        # successful or failed Union Find operations

        # Initializing Our Union Find
        # 
        uf = UnionFind(n)
        
        # Global Cost From All Edges Added
        total_cost = 0

        # Global Number of Total Edges
        edges_used = 0

        # Iterate over all edges (already sorted smallest to largest)
        for cost, i, j in edges:

            # Union succeeds ONLY if no cycle formed
            if uf.union(i, j):

                # No cycle, we have found smallest edge to add
                total_cost += cost
                edges_used += 1


                # MST Exit:
                # MST has been generated once the smallest n-1 edges have been chosen
                if edges_used == n - 1:
                    break


        # overall: tc O(n^2 log n)
        # overall: sc: P(n^2)
        return total_cost

    def minCostConnectPoints(self, points: List[List[int]]) -> int:

        # Prim's Algorithm (Minimum Spanning Tree)
        # Node based greedy expansion (no explicit cycle detection)
        # Always add the cheapest edge connecting the current MST to a new node

        # Difference from Kruskal:
        # Node based expansion (not edge based)
        # No explicit cycle detection needed

        n = len(points)

        # Connection Weight Map:
        # To check if a cheaper edge connecting node to MST has been found,
        # initialize weight to each node to 'inf' to start
        # sc: O(V)
        min_dist = [float('inf')] * n
        
        # Track nodes already included in MST
        # to avoid cycles?
        # sc: O(V)
        visited = [False] * n

        # Initialize MST:
        # starting node has weight of 0
        min_dist[0] = 0

        # MinHeap: (edge_cost, node)
        # Will keep track of edges tracking the min weight,
        # ensures the smallest connecting edge is expanded to next
        # sc: O(V)
        minHeap = []

        minHeap.append((0,0))

        # Global weight cost between all edges
        total_cost = 0
    
        # Prim Traversal (Greedy Expansion)
        # always expand lowest cost frontier edge
        # tc: O(n^2 log n)
        while minHeap:

            # Grab cheapest node on the minHeap
            cost, u = heapq.heappop(minHeap)
            
            # Skip if node are already connected to MST
            if visited[u]:
                continue

            # New node found:

            # Process Node: 
            # add node to tree, add edge cost to global cost
            visited[u] = True
            total_cost += cost

            # Explore New Node Neighbor Edges:
            # Dynamically compute distance to all unvisited nodes 
            for v in range(n):

                # New node has neighbor not in MST
                if not visited[v]:

                    # Calculate distance between new node and its neighbor
                    # two points we are getting distance between
                    x1, y1 = points[u]
                    x2, y2 = points[v]

                    # Manhattan Distance = |x1 - x2| + |y1 - y2|
                    # where point 1 = (x1, y1)
                    #       point 2 = (x2, y2)
                    dist = abs(x1 - x2) + abs(y1 - y2)
                    
                    # if cheaper connection to neighbor found than current connection,
                    # push edge to heap for processing
                    if dist < min_dist[v]:

                        # weight to connect to neighbor
                        min_dist[v] = dist

                        # push edge to heap for processing
                        heapq.heappush(minHeap,(dist, v))

        # overall: tc O(n^2 log n)
        # overall: sc O(n)
        return total_cost

    class UnionFind:
        def __init__(self, n):
            # Each node starts as its own parent (separate component)
            # sc: O(n)
            self.parent = list(range(n))
            # Rank approximates tree depth (for balancing)
            # sc: O(n)
            self.rank = [0] * n

        def find(self, x):
            # Find root representative of component
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])  # Path compression
            return self.parent[x]

        def union(self, x, y):
            xr, yr = self.find(x), self.find(y)
            if xr == yr:
                return False
            if self.rank[xr] < self.rank[yr]:
                self.parent[xr] = yr
            elif self.rank[xr] > self.rank[yr]:
                self.parent[yr] = xr
            else:
                self.parent[yr] = xr
                self.rank[xr] += 1
            return True

    class Solution:
        def minCost(self, n: int, edges: list[list[int]], k: int) -> int:
            # Sort edges by weight (ascending)
            # tc: O(E log E)
            edges.sort(key=lambda x: x[2])

            uf = UnionFind(n)
            mst_edges = []

            # Build MST using Kruskal
            # tc: O(E α(n)) ~ O(E)
            for u, v, w in edges:
                if uf.union(u, v):
                    mst_edges.append(w)

            # MST has n-1 edges; remove the k-1 largest to form k components
            mst_edges.sort(reverse=True)  # Sort descending to remove largest
            if k - 1 >= len(mst_edges):
                return 0  # All components are isolated nodes

            # Remove k-1 largest edges
            result = mst_edges[k - 1]  # The new maximum edge in remaining MST
            return result

    # Time Complexity:
    #   - Sorting edges: O(E log E)
    #   - Kruskal union-find: O(E α(n)) ~ O(E)
    #   => overall: O(E log E)
    # Space Complexity:
    #   - Union-Find: O(n)
    #   - MST edges list: O(n)
    #   => overall: O(n)

    def minCostConnectPoints(self, points: List[List[int]]) -> int:

        import heapq

                # Build adjacency list
                # tc: O(E)
                # sc: O(E)
                adj = [[] for _ in range(n)]
                for u, v, w in edges:
                    adj[u].append((v, w))
                    adj[v].append((u, w))

                visited = [False] * n
                minHeap = [(0, 0, -1)]  # (weight, node, parent)
                mst_edges = []

                while minHeap:
                    w, u, parent = heapq.heappop(minHeap)
                    if visited[u]:
                        continue
                    visited[u] = True
                    if parent != -1:
                        mst_edges.append(w)  # Collect MST edge weights

                    for v, weight in adj[u]:
                        if not visited[v]:
                            heapq.heappush(minHeap, (weight, v, u))

                # MST built, now remove k-1 largest edges
                mst_edges.sort(reverse=True)
                if k - 1 >= len(mst_edges):
                    return 0

                return mst_edges[k - 1]

        # Time Complexity:
        #   - Heap operations: O(E log V)
        #   - Sorting MST edges: O(V log V)
        #   => overall: O(E log V)
        # Space Complexity:
        #   - Adjacency list: O(E)
        #   - MinHeap: O(V)
        #   => overall: O(E + V)