#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define NMAX 200005

int S;
int PMD[ NMAX ];
struct Nod { int x, y, c; } V[ NMAX ];
vector < pair < int, int > > sol;

void PMDinitializare ( int n );
void APM ( int n, int m );

int main() {

    freopen( "apm.in", "r", stdin );
    freopen( "apm.out", "w", stdout );

    int n, m, i, j, x, y, c;

    scanf( "%d%d",&n,&m );
    for ( i = 1; i <= m; ++i ) {
        scanf( "%d%d%d",&x,&y,&c );
        V[ i ] = { x, y, c };
    }

    PMDinitializare ( n );
    APM ( n, m );

    printf( "%d\n%d\n",S,sol.size() );
    for ( i = 0; i < sol.size(); ++i ) {
        printf( "%d %d\n",sol[ i ].first, sol[ i ].second );
    }

    return 0;

}

void PMDinitializare ( int n ) {
    int i;
    for ( i = 1; i <= n; ++i ) PMD[ i ] = i;
}

bool cmp ( Nod a, Nod b ) {  return a.c < b.c; }

int Root ( int x ) {

    while ( PMD[ x ] != PMD[ PMD[ x ] ] ) {
        PMD[ x ] = PMD[ PMD[ x ] ];
    }

    return PMD[ x ];

}

void APM ( int n, int m ) {

    int i, j, x, y, rx, ry;

    sort( V + 1, V + 1 + m, cmp );
    for( i = 1; i <= m; ++i ) {
        rx = Root( V[ i ].x );
        ry = Root( V[ i ].y );
        if ( rx != ry ) {
            S += V[ i ].c;
            PMD[ rx ] = ry;
            sol.push_back( { V[ i ].x, V[ i ].y } );
        }
    }

}