#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, m, i, h[200001], tatal[200001], cost;

struct HATZ{
    int a, b, c;
}mh[200005], sol[200005];

int TATA(int k){
    while ( k != tatal[k] )
        return TATA( tatal[k] );
    return k;
}
int muchie ( int r1, int r2 ){
    r1 = TATA( r1 );
    r2 = TATA( r2 );
    if ( r1 == r2 )
        return 0;
    if ( h[r1] < h[r2] )
        tatal[r1] = r2;
    else if ( h[r2] < h[r1] )
        tatal[r2] = r1;
    else {
        tatal[r1] = r2;
        h[r2]++;
    }
    return 1;
}
void kruskal(){
    int k = 1, muchii = 1, r1, r2;
    while ( muchii <= n - 1 ){
        r1 = mh[k].a;
        r2 = mh[k].b;

        if ( muchie( r1, r2 ) ){
            sol[muchii] = mh[k];
            muchii++;
            cost += mh[k].c;
        }
        //cout<<r1<<" "<<r2<<'\n';
        k++;
    }
}
bool compare( HATZ a, HATZ b ){
    if ( a.c < b.c )
        return true;
    return false;
}


int main()
{   f >> n >> m;
    for ( i = 1; i <= m; i++ ){
        f >> mh[i].a >> mh[i].b >> mh[i].c;
    }
    sort( mh + 1, mh + m + 1, compare );
    for ( i = 1; i <= n; i++ ){
        h[i] = 1;
        tatal[i] = i;
    }
    kruskal();
    g << cost << "\n" << n - 1 << "\n";
    for ( i = 1; i <= n - 1; i++ )
        g << sol[i].a << " " << sol[i].b << "\n";



    return 0;
}