#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 2e5;
struct edge {
    int from, to, cost;
    bool operator < ( const edge &other ) const {
        return cost < other.cost;
    }
};
int sef[NMAX + 1];
int sef_suprem ( int node ) {
    if ( sef[node] == node )
        return node;
    return sef[node] = sef_suprem ( sef[node] );
}
vector < edge > graf;
vector < pair < int, int > > result;
ifstream fin ( "apm.in" );
ofstream fout ( "apm.out" );
int main () {
    int n, m, x, y, cost, a, b, sef_a, sef_b, sum;
    fin >> n >> m;
    for ( int i = 1; i <= m; i++ ) {
        fin >> x >> y >> cost;
        graf.push_back ( { x, y, cost } );
    }
    for ( int i = 1; i <= n; i++ )
        sef[i] = i;
    sort ( graf.begin(), graf.end () );
    sum = 0;
    for ( int i = 0, cate = 0; i < m && cate < n - 1; i++ ) {
        a = graf[i].from; b = graf[i].to; cost = graf[i].cost;
        sef_a = sef_suprem ( a ); sef_b = sef_suprem ( b );
        if ( sef_a != sef_b ) {
            sum += cost;
            sef[sef_b] = sef[sef_a];
            result.push_back ( make_pair ( a, b ) );
        }
    }
    fout << sum << '\n';
    fout << n - 1 << '\n';
    for ( auto x: result )
        fout << x.first << ' ' << x.second << '\n';
    
    return 0;
}