#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int NMAX  = 200001;
const int INFI = 0x3f3f3f;


int cost;
vector < pair < int, int > > V[ NMAX ];
vector < pair < int, int > > Sol;
int InApm[ NMAX ];

void Prim( int n ) {

    priority_queue < pair < int, pair < int, int > > > Q;

    for ( int i = 0; i < V[ 1 ].size(); ++i ) {
        Q.push( { -V[ 1 ][ i ].first , { 1, V[ 1 ][ i ].second } } );
    }

    InApm[ 1 ] = 1;

    while ( !Q.empty() ) {
        int x = Q.top().second.first;
        int y = Q.top().second.second;
        int c = -Q.top().first;
        Q.pop();
        if ( InApm[ x ] + InApm[ y ] == 1 ) {
            cost += c;
            Sol.push_back( { x, y } );
            if ( InApm[ x ] ) swap( x, y );
            for ( int i = 0; i < V[ x ].size(); ++i ) {
                Q.push( { -V[ x ][ i ].first, { x, V[ x ][ i ].second } } );
            }
            InApm[ x ] = InApm[ y ] = 1;
        }
    }


}

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 );
    while ( m-- ) {
        scanf( "%d%d%d", &x,&y,&c );
        V[ x ].push_back( { c, y } );
        V[ y ].push_back( { c, x } );
    }

    Prim( n );
    printf( "%d\n%d\n",cost, n - 1 );
    for ( int i = 0; i < Sol.size(); ++i ) {
        printf( "%d %d\n", Sol[ i ].first, Sol[ i ].second );
    }


    return 0;

}