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

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();

        Graph G = new Graph();
        G.initialize(N);

        for (int i = 0; i < M; i++) {
            int x, y, w;
            x = in.nextInt();
            y = in.nextInt();
            w = in.nextInt();

            G.addEdge(x, y, w);
            G.addEdge(y, x, w);
        }

        PrimMST mst = new PrimMST(G);
        mst.getMST();
    }


    static class Graph{

        private static class Edge{
            int node;
            int cost;
            int next;

            Edge(int node, int cost, int next){
                this.node = node;
                this.cost = cost;
                this.next = next;
            }
        }

        final static int NIL = -1;
        private int[] head;
        private ArrayList<Edge> graph;

        private int N;
        private int contor;

        void initialize(final int N){
            head = new int[N];
            graph = new ArrayList<>();

            System.gc();

            this.N = N;
            this.contor = 0;

            for (int i = 0; i < N; ++i)
                head[i] = NIL;
        }

        void addEdge(int x, int y, int w){
            x--; y--;
            graph.add(new Edge(y, w, head[x]));
            head[x] = contor++;
        }

        int getHead(int node){
            node--;
            return head[node];
        }

        int getCost(int p){
            assert 0 <= p && p < contor;
            return graph.get(p).cost;
        }

        int getNext(int p){
            assert 0 <= p && p < contor;
            return graph.get(p).next;
        }

        int getNeighbour(int p){
            assert 0 <= p && p < contor;
            return graph.get(p).node + 1;
        }

        int getNumberOfNodes(){
            return N;
        }
    }

    static class PrimMST {
        private class Node{
            long distance;
            int node;

            Node(long distance, int node) {
                this.distance = distance;
                this.node = node;
            }
        }

        private Graph graph;
        private int N;
        private long[] dist;
        private boolean[] visited;
        private int[] father;


        PrimMST(Graph G){
            graph = G;
            this.N = graph.getNumberOfNodes();
            dist = new long[this.N + 1];
            visited = new boolean[this.N + 1];
            father = new int[this.N + 1];
        }

        void getMST() throws IOException{
            Queue<Node> minHeap = new PriorityQueue<Node>(new Comparator<Node>() {
                @Override
                public int compare(Node o1, Node o2) {
                    return Long.compare(o1.distance, o2.distance);
                }
            });

            Arrays.fill(dist, Long.MAX_VALUE);
            Arrays.fill(visited, false);
            Arrays.fill(father, -1);

            dist[1] = 0;
            minHeap.add(new Node(0, 1));

            long valueMST = 0;

            while (!minHeap.isEmpty()){
                Node _node = minHeap.remove();
                int node = _node.node;

                if (dist[node] != _node.distance)
                    continue;

                valueMST += dist[node];
                visited[node] = true;

                for (int p = graph.getHead(node); p != Graph.NIL; p = graph.getNext(p)) {
                    int son = graph.getNeighbour(p);
                    int cost = graph.getCost(p);

                    if (dist[son] > cost && !visited[son]){
                        dist[son] = cost;
                        father[son] = node;
                        minHeap.add(new Node(dist[son], son));
                    }
                }
            }

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

            out.println(valueMST);
            out.println(this.N - 1);

            for (int i = 2; i <= N; i++) {
                out.println(i + " " + father[i]);
            }

            out.close();
        }
    }


    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();
        }
    }
}