import java.io.*;

public class Main {

    static StreamTokenizer in;
    static PrintWriter out;

    public static void main(String[] args) throws IOException {

        in = new StreamTokenizer(new BufferedReader(new FileReader("apm.in")));
        out = new PrintWriter(new BufferedWriter(new FileWriter("apm.out")));

        int noduri;
        int muchii;

        int min;
        int u = 0, v = 0;
        int x, y;
        int total = 0;
        int contorMuchiiGasite = 0;

        in.nextToken();
        noduri = (int) in.nval;
        in.nextToken();
        muchii = (int) in.nval;
        int[][] matrice = new int[noduri + 1][noduri + 1];
        int[] vizitat = new int[noduri + 1];
        int[] muchiiGasite = new int[(noduri - 1) * 3];
        int nrMuchii = 0;

        for (int i = 1; i <= muchii; i++) {
            in.nextToken();
            x = (int) in.nval;
            in.nextToken();
            y = (int) in.nval;
            in.nextToken();
            matrice[x][y] = (int) in.nval;
            matrice[y][x] = matrice[x][y];
        }

        for (int i = 1; i <= noduri; i++) {
            vizitat[i] = 0;
            for (int j = 1; j <= noduri; j++) {
                if (matrice[i][j] == 0) {
                    matrice[i][j] = 999;
                }
            }
        }

        vizitat[1] = 1;
        for (int contor = 1; contor <= noduri - 1; contor++) {
            min = 999;
            for (int i = 1; i <= noduri; i++) {
                if (vizitat[i] == 1) {
                    for (int j = 1; j <= noduri; j++) {
                        if (vizitat[j] == 0) {
                            if (min > matrice[i][j]) {
                                min = matrice[i][j];
                                u = i;
                                v = j;
                            }
                        }
                    }
                }
            }
            total += min;
            nrMuchii++;
            vizitat[v] = 1;

            muchiiGasite[contorMuchiiGasite] = u;
            muchiiGasite[contorMuchiiGasite + 1] = v;
            contorMuchiiGasite += 2;
        }
        out.println(total);
        out.print(nrMuchii);
        for (int i = 0; i < contorMuchiiGasite; i += 2) {
            out.print("\n"+ muchiiGasite[i]);
            out.print(" " + muchiiGasite[i + 1]);
        }
        out.close();
    }


}