#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin ( "apm.in" );
ofstream fout ( "apm.out" );

const int N = 5e6;

struct muchie {
    int a;
    int b;
    long long cost;
} v[N], ans[N];

bool cmp ( muchie a, muchie b ) {
    return a.cost < b.cost;
}

int sup[N];

int suprem ( int x ) {
    if ( x == sup[x] )
        return x;
    else {
        sup[x] = suprem(sup[x]);
        return sup[x];
    }
}

int main () {
    
    int n, m;
    
    fin >> n >> m;
    
    for ( int i = 0; i < m; i++ ) {
        
        fin >> v[i].a >> v[i].b >> v[i].cost;
        
        sup[v[i].a] = v[i].a;
        sup[v[i].b] = v[i].b;
    }
    
    sort (v, v + m, cmp);
    
    int cnt = 0;
    long long s = 0;
    
    for ( int i = 0; i < m; i++ ) {
        
        if ( suprem(v[i].a) != suprem(v[i].b) ) {
            
            sup[suprem(v[i].a)] = sup[suprem(v[i].b)];
            ans[cnt] = v[i];
            
            s = s + v[i].cost;
            cnt++;
        }
    }
    
    fout << s << "\n" << cnt << "\n";
    
    for ( int i = 0; i < cnt; i++ )
        fout << ans[i].a << " " << ans[i].b << "\n";
    
    return 0;
}