# include <fstream>
# include <algorithm>
# include <vector>
# include <queue>
# define fi second.first
# define sec second.second
# define PII pair< int, int >

using namespace std;

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

int n, m;
int total;
vector < vector < PII > > A;
vector < bool > v;
vector < PII > answer;

void Read() {

    f >> n >> m;
    A.resize( n + 1 );
    v.resize( n + 1 );
    for ( int i = 0; i < m; ++ i ) {
        int x, y, c; f >> x >> y >> c;
        A[x].push_back( make_pair( y, c ) );
        A[y].push_back( make_pair( x, c ) );
    }
}

void Prim() {

    priority_queue < pair < int, PII > > q;

    v[1] = true;
    for ( auto it: A[1] ) {
        q.push( make_pair( -it.second, make_pair( 1, it.first ) ) );
    }

    int k = 0;;
    while( k < n - 1 && !q.empty() ) {

        int cost = q.top().first;
        int a = q.top().fi;
        int b = q.top().sec;
        q.pop();

        if( v[b] == false ) {
            ++ k;
            answer.push_back( make_pair( a, b ) );
            v[b] = true;
            total = total - cost;
            for ( auto it: A[b] ) {
                if ( v[it.first] == false ) {
                    q.push( make_pair( -it.second, make_pair( b, it.first ) ) );
                }
            }
        }
    }
}

void Afisare() {
    g << total << '\n';
    g << n - 1 << '\n';
    for ( auto it: answer ) {
        g << it.first << " " << it.second << '\n';
    }
}

void Solve() {

    Read();
    Prim();
    Afisare();
}

int main()
{
    Solve();

    return 0;
}