> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/1135.-connecting-cities-with-minimum-cost.md).

# 1135. Connecting Cities With Minimum Cost

There are `N` cities numbered from 1 to `N`.

You are given `connections`, where each `connections[i] = [city1, city2, cost]` represents the cost to connect `city1` and `city2` together.  (A *connection* is bidirectional: connecting `city1` and `city2` is the same as connecting `city2` and `city1`.)

Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together.  The cost is the sum of the connection costs used. If the task is impossible, return -1.

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/04/20/1314_ex2.png)

```
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:**

![](https://assets.leetcode.com/uploads/2019/04/20/1314_ex1.png)

```
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.
```

**Note:**

1. `1 <= N <= 10000`
2. `1 <= connections.length <= 10000`
3. `1 <= connections[i][0], connections[i][1] <= N`
4. `0 <= connections[i][2] <= 10^5`
5. `connections[i][0] != connections[i][1]`

```cpp
// Kruskal’s Algorithm + Union => Minimum Spanning Tree
int findRoot(vector<int>& roots, int i) {
    return i == roots[i] ? i : roots[i] = findRoot(roots, roots[i]);
}
int minimumCost(int N, vector<vector<int>>& connections) {
    vector<int> roots(N + 1), cnt(N + 1, 1);
    for (int i = 0; i <= N; ++i) roots[i] = i;
    sort(connections.begin(), connections.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[2] < b[2];
    });
    int res = 0, n = N;
    for (const vector<int>& c : connections) {
        int r1 = findRoot(roots, c[0]), r2 = findRoot(roots, c[1]);
        if (r1 != r2) {
            res += c[2];
            if (cnt[r1] >= cnt[r2]) {
                roots[r2] = r1;
                cnt[r1] += cnt[r2];
            } else {
                roots[r1] = r2;
                cnt[r2] += cnt[r1];
            }
            --n;
        }
    }
    return n == 1 ? res : -1;
}
```