import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        //这次用kruskal算法做
        //思路：找到最短的边，然后找次短的边，
        //用并查集的思想判断这个边和它的终点是否相同，
        //若相同，就不要，
        //若不同，就加入集合，
        //直到找到n-1条边
        int sum = 0;
        Arrays.sort(cost, Comparator.comparingInt(o -> o[2]));
        //新建一个ArrayList存储边，以便于遍历时将不会用到的边删除，即剪枝。
        ArrayList<int[]> edges = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            edges.add(cost[i]);
        }
        sum += edges.get(0)[2];
        //建立一个数组用来实现并查集,初始时，每个点的终点是他本身
        int[] ends = new int[n+1];
        for (int i = 0; i < n+1; i++) {
            ends[i] = i;
        }
        //将最短边的两点终点设为同一个点
        int start = edges.get(0)[0];
        ends[start] = edges.get(0)[1];
        int index = 1;
        int a;
        int b;
        //新建一个集合用来剪枝，删除不会再用的边
        ArrayList<Integer> delete = new ArrayList<>();
        while (index < n-1){
            for (int i = 0; i < m; i++) {
                a = edges.get(i)[0];
                b = edges.get(i)[1];
                if(findEnd(ends,a)!=findEnd(ends,b)){
                    //将终点合一
                    ends[findEnd(ends,a)] = ends[b];
                    sum += edges.get(i)[2];
                    break;
                }else {
                    delete.add(i);
                }
            }
            index++;
            //将不用的边删除
            for (int i = delete.size() - 1; i >= 0; i--) {
                edges.remove(delete.get(i).intValue());
            }
            delete.clear();
        }
        return sum;
    }
    public int findEnd(int[] ends, int i){
        while (ends[i]!=i){
            i = ends[i];
        }
        return i;
    }
}