#include <algorithm>
#include <fstream>

using namespace std;

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

int n, m;
long long ct;
int ns, vs[205000], i;
int ind[400005], x[400005], y[400005], c[400005];
int gr[200005];

int grupa(int x){
    int r = x, y;
    while (r != gr[r])
        r = gr[r];

    while (x != gr[x]){
        y = gr[x];
        gr[x] = r;
        x = y;
    }
    return r;
}

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

bool cmp(int x, int y){
    return c[x] < c[y];
}

int main(){
    f >> n >> m;
    for (i = 1; i <= n; i++)
        gr[i] = i;

    for (i = 1; i <= m; i++){
        f >> x[i] >> y[i] >> c[i];
        ind[i] = i;
    }
    sort(ind+1, ind+m+1, cmp);
    for (i = 1; i <= m; i++){
        if (grupa(x[ind[i]])!= grupa(y[ind[i]])){
            ct += c[ind[i]];
            adaug(x[ind[i]], y[ind[i]]);
            ns++;
            vs[ns] = ind[i];
        }
    }
    g << ct << '\n' << n-1 << '\n';
    for (i = 1; i <= n-1; i++)
        g << x[vs[i]] << ' ' << y[vs[i]] << '\n';
    return 0;
}