题解 | #【模板】最小生成树#

import java.io.*;
import java.util.*;
import java.math.BigInteger;

public class Main {
    static class Edge {
        int u, v, w, index;
        public Edge(int u, int v, int w, int index) {
            this.u = u;
            this.v = v;
            this.w = w;
            this.index = index;
        }
    }
    
    static class UnionFind {
        int[] parent, rank;
        
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }
        
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
                return true;
            }
            return false;
        }
    }

    static void solve() {
        int n = in.nextInt(),m = in.nextInt();
        List<Edge> edges = new ArrayList<>();
        
        for (int i = 1; i <= m; i++) {
            int u = in.nextInt() - 1;  
            int v = in.nextInt() - 1;
            int w = in.nextInt();
            edges.add(new Edge(u, v, w, i));
        }

        edges.sort(Comparator.comparingInt(a -> a.w));

        UnionFind uf = new UnionFind(n);
        long mWeight = 0;
        List<Integer> mEdges = new ArrayList<>();

        for (Edge edge : edges) {
            if (uf.union(edge.u, edge.v)) {
                mWeight += edge.w;
                mEdges.add(edge.index);
                if (mEdges.size() == n - 1) {
                    break;
                }
            }
        }
        out.println(mWeight);
        for (int i = 0; i < mEdges.size(); i++) {
            out.print(mEdges.get(i) + " ");
        }
    }

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    static FastReader in = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);

    static class FastReader {
        static BufferedReader br;
        static StringTokenizer st;

        FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            String str = "";
            while (st == null || !st.hasMoreElements()) {
                try {
                    str = br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st = new StringTokenizer(str);
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}