#include <algorithm>
#include <fstream>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int nmax= 200000;
const int mmax= 400000;

int n, m, ans, k;

struct str {
    int x, y, c;
};

int r[nmax+1], sol[nmax+1];
str edge[mmax+1];

bool cmp( str x, str y ) {
    return x.c<y.c;
}

inline int root( int x ) {
    if ( x!=r[x] ) {
        return r[x]= root(r[x]);
    }
    return x;
}

int main(  ) {
    fin>>n>>m;
    for ( int i= 1; i<=m; ++i ) {
        fin>>edge[i].x>>edge[i].y>>edge[i].c;
    }

    sort( edge+1, edge+m+1, cmp );

    for ( int i= 1; i<=n; ++i ) {
        r[i]= i;
    }
    for ( int i= 1; i<=m; ++i ) {
        int rx= root(edge[i].x), ry= root(edge[i].y);
        if ( rx!=ry ) {
            ans+= edge[i].c;
            r[ry]= rx;
            sol[++k]= i;
        }
    }

    fout<<ans<<"\n"<<k<<"\n";
    for ( int i= 1; i<=k; ++i ) {
        fout<<edge[sol[i]].x<<" "<<edge[sol[i]].y<<"\n";
    }

    return 0;
}