5 6
1 2 2
1 3 7
1 4 6
2 3 1
3 4 3
3 5 2

8
• 1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: LiangXinRui
 * @Date: 2023/3/3 9:07
 * @Description: Kruskal算法在找最小生成树结点之前，需要对权重从小到大进行排序。
 * 将排序好的权重边依次加入到最小生成树中（如果加入时产生回路就跳过这条边，加入下一条边），
 * 当所有的结点都加入到最小生成树中后，就找到了这个连通图的最小生成树～
 */
public class demo83_kruskal_修建公路 {
    static final int N = 300005;
    static int n,m,count;
    static long sum;
    static Edge[] edges = new Edge[N];
    static int[] pre = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int find(int v) {
        if (v != pre[v]) {
            pre[v] = find(pre[v]);
        }
        return pre[v];
    }
    public static void main(String[] args) throws Exception {
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 1; i <= n; i++) {
            pre[i] = i;
        }
        for (int i = 0; i < m; i++) {
            String[] s1 = br.readLine().split(" ");
            int a, b, c;
            a = Integer.parseInt(s1[0]);
            b = Integer.parseInt(s1[1]);
            c = Integer.parseInt(s1[2]);
            edges[i] = new Edge(a, b, c);
        }
        Arrays.sort(edges, 0, m);
        for (int i = 0; i < m; i++) {
            int a = edges[i].a;
            int b = edges[i].b;
            int w = edges[i].w;
            a = find(a);
            b = find(b);
            if (a != b) {//这里不能写成 if (find(a) != find(b))
                pre[a] = b;
                sum += w;
                count++;
            }
        }
        if (count == n - 1) {
            System.out.println(sum);
        } else {
            System.out.println(-1);
        }
    }
    static class Edge implements Comparable<Edge> {
        int a;
        int b;
        int w;
        Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
        public int compareTo(Edge e) {
            return w - e.w;
        }
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
 * @Author: LiangXinRui
 * @Date: 2023/03/02/20:16
 * @Description:
 */
public class demo83_prim_堆优化 {
    static int[] head, next, ends, pre;
    static int n, m, num, total, begin;
    static double sum;
    static double[] weights, dis;
    static boolean[] vis;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static class pair {
        double first;//记录 边权
        int second;//记录 下一个结点
        public pair() {
        }
        public pair(double first, int second) {
            this.first = first;
            this.second = second;
        }
    }
    //自定义比较类，升序排列
    static Comparator<pair> comparator = (o1, o2) -> o1.first - o2.first > 0 ? 1 : 0;
    static Queue<pair> queue = new PriorityQueue<>(comparator);
    static void add(int start, int end, int weight) {
        ends[total] = end;
        weights[total] = weight;
        next[total] = head[start];
        head[start] = total;
        total++;
    }
    static void prim() {
        queue.offer(new pair(weights[0], ends[0]));
        vis[begin] = true;
        while (!queue.isEmpty() && num < n) {
            double len = queue.peek().first;
            int to = queue.peek().second;
            queue.poll();
            if (!vis[to]) {
                sum += len;
                num++;// 找到一条边
                vis[to] = true;// 标记一下，表示我这条边已经用过
                for (int i = head[to]; i != -1; i = next[i]) {
                    if (weights[i] < dis[ends[i]]) {// 如果当前边权小，更新
                        dis[ends[i]] = weights[i];
                        queue.offer(new pair(weights[i], ends[i]));// 把新的边权和结点加入队列
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        String[] firstStr = br.readLine().split(" ");
        n = Integer.parseInt(firstStr[0]);
        m = Integer.parseInt(firstStr[1]);
        dis = new double[n + 1];
        head = new int[2 * m + 1];//表示以 i 为起点的最后一条边的编号
        next = new int[2 * m + 1];//存储与当前边起点相同的上一条边的编号
        ends = new int[2 * m + 1];//存储边的终点
        weights = new double[2 * m + 1];//存储边的权值
        vis = new boolean[2 * m + 1];
        Arrays.fill(head, -1);//初始化
        for (int i = 1; i <= n; i++) {
            dis[i] = Double.MAX_VALUE / 2;
        }
        for (int i = 0; i < m; i++) {
            String[] secondStr = br.readLine().split(" ");
            int start = Integer.parseInt(secondStr[0]);
            if (i == 0) begin = start;
            int end = Integer.parseInt(secondStr[1]);
            int weight = Integer.parseInt(secondStr[2]);
            add(start, end, weight);
            add(end, start, weight);
        }
        prim();
        if (n - 1 == num) {
            System.out.printf("%.0f", sum);
        } else {
            System.out.println("-1");
        }
    }
}