#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, tata[200005], cost_total, nr_muchii;
struct muchie { int u, v, c; } mch[400005], sol[200005];
int rad(int nod) {
    int r = nod;
    while(r != tata[r]) r = tata[r];
    int p = nod;
    while(p != r) { int aux = tata[p]; tata[p] = r; p = aux; }
    return r;
}
void qsort_muchii(int st, int dr) {
    int i = st, j = dr;
    muchie piv = mch[(st + dr) / 2];
    while(i <= j) {
        while(mch[i].c < piv.c) i++;
        while(mch[j].c > piv.c) j--;
        if(i <= j) {
            muchie aux = mch[i]; mch[i] = mch[j]; mch[j] = aux;
            i++; j--;
        }
    }
    if(st < j) qsort_muchii(st, j);
    if(i < dr) qsort_muchii(i, dr);
}
int main() {
    fin >> n >> m;
    for(int i = 0; i < m; i++)
        fin >> mch[i].u >> mch[i].v >> mch[i].c;
    qsort_muchii(0, m - 1);
    for(int i = 1; i <= n; i++) tata[i] = i;
    for(int i = 0; i < m; i++) {
        int r1 = rad(mch[i].u), r2 = rad(mch[i].v);
        if(r1 != r2) {
            tata[r1] = r2;
            cost_total += mch[i].c;
            sol[nr_muchii++] = mch[i];
        }
    }
    fout << cost_total << "\n" << nr_muchii << "\n";
    for(int i = 0; i < nr_muchii; i++)
        fout << sol[i].u << " " << sol[i].v << "\n";
    return 0;
}