#include <fstream>
#include <algorithm>

using namespace std;

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

int ind[400005], x[400005], y[400005], c[400005];
int grupa[400005], sol, vsol[400005], ns, n , m, i;

int colectiv(int x){
    int r = x, y;
    while (grupa[r] != r)
        r = grupa[r];
    while (grupa[x] != x){
        y = grupa[x];
        grupa[x] = r;
        x = y;
    }
    return r;
}

void pune(int x, int y){
    int a = colectiv(x), b = colectiv(y);
    grupa[a] = b;
}

bool cmp(int a, int b){
    return c[a] < c[b];
}

int main(){
    f >> n >> m;
    for (i = 1; i <= m; i++){
        f >> x[i] >> y[i] >> c[i];
        ind[i] = i;
    }
    for (i = 1; i <= n; grupa[i] = i, i++);

    sort(ind+1, ind+m+1, cmp);
    for (i = 1; i <= m; i++){
        if (colectiv(x[ ind[i] ]) != colectiv(y[ ind[i] ])){
            sol += c[ind[i]];
            pune(x[ind[i]], y[ind[i]]);
            ns++;
            vsol[ns] = ind[i];
        }
    }
    g << sol << '\n' << n-1 << '\n';
    for (i = 1; i < n; i++)
        g << x[vsol[i]] << ' ' << y[vsol[i]] << '\n';
    return 0;
}