#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
 
struct muchie {
    int a, b;
    int cost;
};
 
inline bool comp(muchie a, muchie b) {
    return a.cost < b.cost;
}
 
int n, m;
int mult[200001];
int adanc[200001];
muchie muchii[400001];
int arbore[200001];
 
int find(int nod) {
    if(mult[nod] != nod)
        mult[nod] = find(mult[nod]);
    return mult[nod];
}
 
inline void add(int a, int b) {
    int rada = find(a);
    int radb = find(b);
    if(adanc[rada] > adanc[radb])
        mult[radb] = mult[rada];
    else if(adanc[rada] < adanc[radb])
        mult[rada] = mult[radb];
    else {
        mult[rada] = mult[radb];
        adanc[radb]++;
    }
}
 
int main(void) {
    ifstream fin("apm.in");
    fin >> n >> m;
     
    for(int i = 0; i < m; ++i)
        fin >> muchii[i].a >> muchii[i].b >> muchii[i].cost;
    fin.close();
     
    int rasp = 0;
    sort(muchii, muchii + m, comp);
    for(int i = 1; i <= n; ++i) {
        mult[i] = i;
        adanc[i] = 0;
    }
     
    for(int i = 0, ind = 0; ind < n - 1; ++i) {
        if(find(muchii[i].a) != find(muchii[i].b)) {
            rasp += muchii[i].cost;
            add(muchii[i].a, muchii[i].b);
            arbore[ind++] = i;
        }
    }
     
    ofstream fout("apm.out");
    fout << rasp << '\n' << n - 1 << '\n';
    for(int i = 0; i < n - 1; ++i)
        fout << muchii[arbore[i]].a << ' ' << muchii[arbore[i]].b << '\n';
    fout.close();
}