#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muc{
    int x, y, cost;
};
muc muchii[400005], sol[200005];
int prov[200005], n, m, k;
long long costtot;
bool cmp( muc a, muc b ){
    if( a.cost < b.cost )
        return true;
    return false;
}
int gas( int x ){
    if( prov[x] == x )
        return x;
    return prov[x]=gas(prov[x]);
}
void uni( int x, int y ){
    x=gas(x);
    y=gas(y);
    if( x != y )
        prov[x]=y;
}
int main(){
    int i;
    fin>>n>>m;
    for( i = 1; i <= m; i++ )
        fin>>muchii[i].x>>muchii[i].y>> muchii[i].cost;
    sort( muchii + 1, muchii + m + 1, cmp );
    for( i = 1; i <= n; i++ )
        prov[i]=i;
    for( i = 1; i <= m && k < n - 1; i++ )
        if( gas(muchii[i].x) != gas(muchii[i].y) ) {
            uni(muchii[i].x,muchii[i].y);
            sol[++k]=muchii[i];
            costtot+=muchii[i].cost;
        }
    fout<<costtot<<endl<<k;
    for( i = 1; i <= k; i++ )
        fout<<sol[i].x<<' '<<sol[i].y;
    return 0;
}