#include <fstream>
#include <algorithm>
#define f in
#define g out
#define cost first
#define x second.first
#define y second.second

using namespace std;
ifstream in ( "apm.in" );
ofstream out( "apm.out" );
pair < int, pair < int, int > > v[400009];
int n, m, i, much, total, rx, ry, t[200009];
pair < int, int > sol[200009];

int rad ( int a ){
    while ( t[a] > 0 )
        a = t[a];
    return a;
}

int main() {
    f>>n>>m;
    for ( i=1; i <= m; i++ )
        f>>v[i].x>>v[i].y>>v[i].cost;
    sort( v+1, v+m+1 );
    for ( i=1; i <= m && much < n; i++ ){
        rx = rad ( v[i].x );
        ry = rad ( v[i].y );
        if ( rx == ry )
            continue;
        if ( t[rx] < t[ry] ){
            t[rx] += t[ry];
            t[ry] = rx;
        } else {
            t[ry] += t[rx];
            t[rx] += ry;
        }
        much++;
        sol[much].first = v[i].x; sol[much].second = v[i].y;
        total += v[i].cost;
    }
    g<<total<<"\n"<<n-1<<"\n";
    for ( i=1; i < n; i++ )
        g<<sol[i].first<<" "<<sol[i].second<<"\n";
    return 0;
}