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

using namespace std;

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

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

muchie vmuc[NMAX];

void citire() {
    int i;
    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;
}

void afis2() {
    int i;
    for (i = 1; i <= n; i++)
        fout << mult[i] << " ";
    fout << endl;
}

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

void arbore() {
    int i, j, k, vfx, vfy, nrmuc;
    for (i = 1; i <= n; i++)
        mult[i] = i;
    //afis2();
    // nu avem nici o muchie selectata
    nrmuc = 0; k = 0;
    do {
        // daca cele doua varfuri nu apartin aceuasi componente
        if (mult[vmuc[k].x] != mult[vmuc[k].y]) {
            vfy = mult[vmuc[k].y];
            vfx = mult[vmuc[k].x];
            //unim cele doua subcomponente
            for (j = 1; j <= n; j++)
                if (mult[j] == vfx)
                    mult[j] = vfy;
            nrmuc++; lgdrum += vmuc[k].cost;
            //fout << vmuc[i].x << " " << vmuc[i].y << " " << vmuc[i].cost << "\n";
            vmuc[k].marc = 1;
            //afis2();
        }
        k++;
    } 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;
}