#include <iostream>
#include <fstream>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m, sir[3][400001], aux, smin, sol[2][200001], v[200001], arb[200001], nra;

void citire() {
    f >> n >> m;
    for (int i = 1; i <= m; i++)
        f >> sir[0][i] >> sir[1][i] >> sir[2][i];
}

void ordonare() {
    for (int i = 1; i < m; i++)
        for (int j = i + 1; j <= m; j++)
            if (sir[2][i] > sir[2][j]) {
                    aux = sir[0][i];
                    sir[0][i] = sir[0][j];
                    sir[0][j] = aux;
                    aux = sir[1][i];
                    sir[1][i] = sir[1][j];
                    sir[1][j] = aux;
                    aux = sir[2][i];
                    sir[2][i] = sir[2][j];
                    sir[2][j] = aux;
            }
}

void solve() {
    int nrm = 0;
    for (int i = 1; i <= m; i++) {
        if (nrm == n - 2) break;
        if (v[sir[0][i]] == 0 || v[sir[1][i]] == 0) {
            nrm++;
            sol[0][nrm] = sir[0][i];
            sol[1][nrm] = sir[1][i];
            v[sir[0][i]] = 1;
            v[sir[1][i]] = 1;
            smin = smin + sir[2][i];
            if (arb[sir[0][i]] == 0 && arb[sir[1][i]] == 0)
            {
                nra++;
                arb[sir[0][i]] = nra;
                arb[sir[1][i]] = nra;
            } else {
                int minim;
                int c = 0;
                if (arb[sir[0][i]] != 0) {
                        c = 1;
                        minim = arb[sir[0][i]];
                }
                if (arb[sir[1][i]] != 0 && (arb[sir[1][i]] < minim || minim == 0)) {
                        minim = arb[sir[1][i]];
                        c = 2;
                }

                if (c == 1) {
                    int d = arb[sir[1][i]];
                    if (d != 0) {
                    for (int j = 1; j <= m; j++)
                        if (arb[j] == d) arb[j] = minim;
                    }
                    else arb[sir[1][i]] = minim;
                }
                else  {
                    int d = arb[sir[0][i]];
                    if (d != 0) {
                    for (int j = 1; j <= m; j++)
                        if (arb[j] == d) arb[j] = minim;
                    }
                    else arb[sir[0][i]] = minim;
                }

            }
        }
    }
    if (nrm == n - 2) {
        for (int i = 1; i <= m; i++)
            if (arb[sir[0][i]] != arb[sir[1][i]])
            {
                nrm++;
                sol[0][nrm] = sir[0][i];
                sol[1][nrm] = sir[1][i];
                smin = smin + sir[2][i];
                break;
            }
    }
    g << smin << "\n" << nrm << "\n";
    for (int i = 1; i <= nrm; i++)
        g << sol[0][i] << " " << sol[1][i] << "\n";

}

int main()
{
    citire();
    ordonare();
    solve();
    return 0;
}