#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
#include <list>
#define NMAX 100005

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int i, n, m, lgdrum = 0;

struct muchie {
    int x, y, cost, marc;
};

muchie vmuc[NMAX];

void citire() {
    int i;
    muchie mu;
    fin >> n >> m;
    for (i = 0; i < m; i++)
        fin >> vmuc[i].x >> vmuc[i].y >> vmuc[i].cost;
    fin.close();
}

void afis() {
    int i;
    for (i = 0; i < m; i++) {
        fout << vmuc[i].x << " " << vmuc[i].y << " " << vmuc[i].cost << " - ";
    }
    fout << endl;
}

bool cmp(muchie mx, muchie my) {
    return (mx.cost < my.cost);
}

void arbore() {
    int i, j, varf, mult[NMAX], nrmuc;
    for (i = 1; i <= n; i++)
        mult[i] = i;
    // nu avem nici o muchie selectata
    nrmuc = 0; i = 0;
    do {
        // daca cele doua varfuri nu apartin aceuasi componente
        if (mult[vmuc[i].x] != mult[vmuc[i].y]) {
            varf = vmuc[i].y;
            //unim cele doua subcomponente
            for (j = 1; j <= n; j++)
                if (mult[j] == varf)
                    mult[j] = mult[vmuc[i].x];
            nrmuc++; lgdrum += vmuc[i].cost;
            //fout << vmuc[i].x << " " << vmuc[i].y << " " << vmuc[i].cost << "\n";
            vmuc[i].marc = 1;
        }
        i++;
    } while (nrmuc < n - 1);
    //fout << lgdrum << endl;
}

int main() {
    citire();
    //afis();
    sort(vmuc, vmuc + m, cmp);
    //afis();
    arbore();
    fout << lgdrum << endl;
    fout << n - 1 << endl;
    for (i = 0; i < m; i++)
        if (vmuc[i].marc)
            fout << vmuc[i].x << " " << vmuc[i].y << "\n";
    fout.close();
    return 0;
}