import java.io.*;
import java.util.*;

public class Main {
    static class Task {
        public static final String INPUT_FILE = "apm.in";
        public static final String OUTPUT_FILE = "apm.out";
        private static boolean[] used;
        private static int totalEdge = 0;

        int n;
        int m;
        int[] parent;
        int[] size;

        private static class Edges {
            public int node1;
            public int node2;
            public int cost;

            Edges(int _node1, int _node2, int _cost) {
                node1 = _node1;
                node2 = _node2;
                cost = _cost;
            }
        }


        @SuppressWarnings("unchecked")
        Edges[] edges;

        private void readInput() {
            try {
                Scanner sc = new Scanner(new BufferedReader(new FileReader(
                        INPUT_FILE)));
                n = sc.nextInt();
                m = sc.nextInt();
                edges = new Edges[m];

                for (int i = 0; i < m; i++) {
                    int x, y, w;
                    x = sc.nextInt();
                    y = sc.nextInt();
                    w = sc.nextInt();
                    edges[i] = new Edges(x, y, w);
                }
                parent = new int[n + 1];
                size = new int[n + 1];
                used = new boolean[m];
                for (int i = 1; i <= n; i++) {
                    parent[i] = i;
                    size[i] = 1;
                }
                sc.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        private void writeOutput(int result) {
            try {
                BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(OUTPUT_FILE));
                bufferedWriter.write(result + "\n");
                bufferedWriter.write(totalEdge + "\n");
                for(int i = 0; i < m; i++){
                    bufferedWriter.write(edges[i].node1 + " " + edges[i].node2 + "\n");
                }

                bufferedWriter.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        private int findRoot(int node) {
            if (node == parent[node]) {
                return node;
            }
            return parent[node] = findRoot(parent[node]);
        }

        private void mergeForests(int root1, int root2) {
            if (size[root1] <= size[root2]) {
                size[root2] += size[root1];
                parent[root1] = root2;
            } else {
                size[root1] += size[root2];
                parent[root2] = root1;
            }
        }



        private int getResult() {
			int min = 0;

            Arrays.sort(edges, new Comparator<Edges>() {
                @Override
                public int compare(Edges o1, Edges o2) {
                    return o1.cost - o2.cost;
                }
            });

            for(int i = 1; i <= n; i++){
                parent[i] = i;
                size[i] = 0;
            }

            for(int i = 0; i < m ; i++){

                if(findRoot(edges[i].node1) != findRoot(edges[i].node2)){
                    mergeForests(edges[i].node1, edges[i].node2);
                    min += edges[i].cost;
                    totalEdge++;
                    used[i] = true;
                }
            }
            return min;
        }

        public void solve() {
            readInput();
            writeOutput(getResult());
        }
    }

    public static void main(String[] args) {
        new Task().solve();
    }
}