There are `n` cities labeled from `1` to `n`. You are given the integer `n` and an array `connections` where `connections[i] = [xi, yi, costi]` indicates that the cost of connecting city `xi` and city `yi` (bidirectional connection) is `costi`.

Return _the minimum **cost** to connect all the_ `n` _cities such that there is at least one path between each pair of cities_. If it is impossible to connect all the `n` cities, return `-1`,

The **cost** is the sum of the connections' costs used.

**Example 1:**

**Input:** n = 3, connections = \[\[1,2,5\],\[1,3,6\],\[2,3,1\]\]
**Output:** 6
**Explanation:** Choosing any 2 edges will connect all cities so we choose the minimum 2.

**Example 2:**

**Input:** n = 4, connections = \[\[1,2,3\],\[3,4,4\]\]
**Output:** -1
**Explanation:** There is no way to connect all cities even if all edges are used.

**Constraints:**

*   `1 <= n <= 104`
*   `1 <= connections.length <= 104`
*   `connections[i].length == 3`
*   `1 <= xi, yi <= n`
*   `xi != yi`
*   `0 <= costi <= 105`


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


def minimumCost(n, connections):
    connections.sort(key=lambda x: x[2])

    parent = list(range(n + 1))

    cost = 0
    edges = 0
    for c in connections:
        root_x = find(parent, c[0])
        root_y = find(parent, c[1])

        if root_x != root_y:
            parent[root_y] = root_x
            cost += c[2]
            edges += 1

        if edges == n - 1:
            break

    return cost if edges == n - 1 else -1
