import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(new FileInputStream("apm.in"));

        int N = in.nextInt();
        int M = in.nextInt();

        Edge[] edges = new Edge[M];

        for (int i = 0; i < M; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            int w = in.nextInt();
            edges[i] = new Edge(x, y, w);
        }

        KruskalMST mst = new KruskalMST(edges, N);
        List<Edge> treeEdges = mst.minimumSpanningTree();

        int totalCost = 0;

        for (Edge edge: treeEdges){
            totalCost += edge.cost;
        }

        PrintWriter out = new PrintWriter(new FileOutputStream("apm.out"));

        out.println(totalCost + "\n" + (N - 1));

        for (Edge edge: treeEdges) {
            out.println(edge.x + " " + edge.y);
        }

        out.close();
    }

    static class DisjointSet {
        private final int[] father;
        private final int[] rank;
        private final int N;

        DisjointSet(int N){
            this.N = N;
            rank = new int[N + 1];
            father = new int[N + 1];

            for (int i = 1; i <= N; i++)
                initialize(i);
        }

        void initialize(int node){
            if (!(1 <= node && node <= N)) throw new AssertionError();
            father[node] = node;
            rank[node] = 1;
        }

        int find(int node){
            if (!(1 <= node && node <= N)) throw new AssertionError();

            if (father[node] == node)
                return node;
            else
                return father[node] = find(father[node]);
        }

        void union(int x, int y){
            x = find(x);
            y = find(y);

            if (x != y){
                if (rank[x] < rank[y])
                    father[x] = y;
                else
                    father[y] = x;

                if (rank[x] == rank[y])
                    rank[x]++;
            }
        }

        boolean connected(int x, int y){
            return find(x) == find(y);
        }
    }

    static class Edge implements Comparable<Edge>{
        int x, y;
        int cost;

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

        public int compareTo(Edge edge){
            return Integer.compare(cost, edge.cost);
        }
    }

    static class KruskalMST {
        private Edge[] edges;
        private final int N;

        public KruskalMST(Edge[] edges, int N) {
            this.edges = Arrays.copyOf(edges, edges.length);
            this.N = N;
        }

        ArrayList<Edge> minimumSpanningTree(){
            Arrays.sort(edges);
            DisjointSet dsu = new DisjointSet(N);

            int totalCost = 0;
            int countEdges = 0;
            ArrayList<Edge> finalEdges = new ArrayList<>();

            for (int i = 0; i < edges.length && countEdges < (N - 1); i++) {
                int x = edges[i].x;
                int y = edges[i].y;

                if (!dsu.connected(x, y)){
                    dsu.union(x, y);
                    totalCost += edges[i].cost;
                    countEdges++;
                    finalEdges.add(edges[i]);
                }
            }

            return finalEdges;
        }
    }


    static class InputReader{
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 65536);
            tokenizer = null;
        }

        private String nextToken() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()){
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
                catch (IOException e){
                    throw new RuntimeException(e);
                }
            }

            return  tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        String nextString(){
            return nextToken();
        }
    }
}