# Commutable Islands

There are **A** islands and there are **M** bridges connecting them. Each bridge has some **cost** attached to it.

We need to find bridges with **minimal cost** such that all islands are connected.

It is guaranteed that input data will contain **at least one** possible scenario in which all islands are connected with each other.

**Input Format:**

```
The first argument contains an integer, A, representing the number of islands.
The second argument contains an 2-d integer matrix, B, of size M x 3:
    => Island B[i][0] and B[i][1] are connected using a bridge of cost B[i][2].
```

**Output Format:**

```
Return an integer representing the minimal cost required.
```

**Constraints:**

```
1 <= A, M <= 6e4
1 <= B[i][0], B[i][1] <= A
1 <= B[i][2] <= 1e3
```

**Examples:**

```
Input 1:
    A = 4
    B = [   [1, 2, 1]
            [2, 3, 4]
            [1, 4, 3]
            [4, 3, 2]
            [1, 3, 10]  ]

Output 1:
    6

Explanation 1:
    We can choose bridges (1, 2, 1), (1, 4, 3) and (4, 3, 2), where the total cost incurred will be (1 + 3 + 2) = 6.

Input 2:
    A = 4
    B = [   [1, 2, 1]
            [2, 3, 2]
            [3, 4, 4]
            [1, 4, 3]   ]

Output 2:
    6

Explanation 2:
    We can choose bridges (1, 2, 1), (2, 3, 2) and (1, 4, 3), where the total cost incurred will be (1 + 2 + 3) = 6.
```

```java
public class Solution {
    static class Pair {
        int x;
        int y;
        int cost;

        Pair(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }

    public int parent(int x, int[] parentArray) {
        while (parentArray[x] != x)
            x = parentArray[x];
        return x;
    }

    public int solve(int n, ArrayList<ArrayList<Integer>> edges) {
        int[] parentArray = new int[n + 1];
        for (int i = 1; i <= n; i++)
            parentArray[i] = i;
        PriorityQueue<Pair> pq = new PriorityQueue<>(((a, b) -> a.cost - b.cost));
        int miniCost = 0;        
        for (ArrayList<Integer> arrList : edges)
            pq.add(new Pair(arrList.get(0), arrList.get(1), arrList.get(2)));
        while (!pq.isEmpty()) {
            Pair pr = pq.poll();
            int parentX = parent(pr.x, parentArray);
            int parentY = parent(pr.y, parentArray);
            if (parentX != parentY) {
                miniCost += pr.cost;
                parentArray[parentX] = parentY;
            }
        }
        return miniCost;
    }
}
```
