#include <algorithm>
#include <fstream>

using namespace std;

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

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

struct str{
    int x, y, d;
};
str v[nmax+1], sol[nmax+1];
int edge[mmax+1], r[nmax+1];

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

bool comp( int i, int j ) {
    if ( v[i].d==v[j].d ) {
        if ( v[i].x==v[j].x ) {
            return v[i].y<v[j].y;
        }
        return v[i].x<v[j].x;
    }
    return v[i].d<v[j].d;
}

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

    sort( edge+1, edge+m+1, comp );
    int sum= 0, k= 0;
    for ( int i= 1; i<=m; ++i ) {
        int x= root(v[edge[i]].x), y= root(v[edge[i]].y);
        if ( x!=y ) {
            sum+= v[edge[i]].d;
            r[y]= r[x];
            ++k;
            sol[k].x= v[edge[i]].x, sol[k].y= v[edge[i]].y;
        }
    }
    
    fout<<sum<<"\n"<<k<<"\n";
    for ( int i= 1; i<=k; ++i ) {
        fout<<sol[i].x<<" "<<sol[i].y<<"\n";
    }
    
    return 0;
}