import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int solution(int n, int[][] costs) {

        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[2], o2[2]);
            }
        });

        return findBestBridge(n, costs);
    }

    private int findBestBridge(int n, int[][] costs) {
        int[] parent = new int[n];
        Arrays.setAll(parent, i -> i);

        int bridgCnt = 0;
        int totalCost = 0;

        for (int i = 0; i < costs.length; i++) {
            int island1 = costs[i][0];
            int island2 = costs[i][1];
            int cost = costs[i][2];

            int island1Parent = findParent(island1, parent);
            int island2Parent = findParent(island2, parent);

            if (island1Parent!=island2Parent) {
                parent[island2Parent] = island1Parent;
                totalCost += cost;
                bridgCnt++;
            }

            if (bridgCnt == n - 1) break;
        }

        return totalCost;
    }

    private static int findParent(int no, int[] parent) {
        if (parent[no] == no) {
            return no;
        }

        return parent[no] = findParent(parent[no], parent);
    }
}