#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

#define f first
#define s second

int n, m, i, j, x, y, c, ans, nod, tati, cost;
bool viz[200010];
list<pair<int, int> > graf[200010];
priority_queue< pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > Q;
pair<int , pair<int, int> > crt;
stack<pair<int, int> > sol;

int main()
{
    fin >> n >> m;
    for ( i = 1 ; i <= m ; i++ ) {
        fin >> x >> y >> c;
        graf[ x ].push_back( make_pair( y , c ) );
        graf[ y ].push_back( make_pair( x , c ) );
    }

    Q.push( make_pair( 0 , make_pair( 0 , 1 ) ) );
    while (!Q.empty()) {
        crt = Q.top(); Q.pop();
        nod = crt.s.s; tati = crt.s.f; cost = crt.f;
        if ( !viz[ nod ] ) {
            ans += cost;
            sol.push( make_pair( tati , nod ) );
            viz[ nod ] = true;
            for ( list<pair<int, int> >::iterator it = graf[ nod ].begin() ; it != graf[ nod ].end() ; it++ ) {
                if ( !viz[ it->f ] )
                    Q.push( make_pair( it->s , make_pair( nod , it->f ) ) );
            }
        }
    }

    fout << ans << '\n';
    fout << sol.size() - 1 << '\n';
    while ( sol.size() > 1 ) {
        fout << sol.top().f << ' ' << sol.top().s << '\n';
        sol.pop();
    }

    return 0;
}