/*
http://www.infoarena.ro/problema/apm
Se determina un arbore partial minim.
*/

#include <algorithm>
#include <fstream>

#define LIM_M 400001
#define LIM_N 200001

using namespace std;

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

struct muchie {
    int inc;
    int sf;
    int cost;
};

muchie sm[LIM_M], arbore[LIM_M];
int n, m, nms, csfm, comp[LIM_N], Rank[LIM_N], j, ca;

void citire() {
    int i;

    fin >> n >> m;
    for (i = 1; i <= m; i++)
        fin >> sm[i].inc >> sm[i].sf >> sm[i].cost;
}

void initcomp() {
    int i;

    for (i = 1; i <= n; i++)
        comp[i] = i;
}

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

int FindSet(int nod) {
    while (comp[nod] != nod)
        nod = comp[nod];
    return comp[nod];
}

void Union(int r1, int r2) { // Se reunesc multimile reprezentate de r1 si r2.
    if (Rank[r1] > Rank[r2])
        comp[r2] = r1;
    else {
        comp[r1] = r2;
        if (Rank[r1] == Rank[r2])
            Rank[r2]++;
    }
}

void rezultat() {
    fout << ca << '\n' << n - 1 << '\n';
    for (int i = 1; i <= nms; i++) // pentru toate muchiile selectate
        fout << arbore[i].inc << ' ' << arbore[i].sf << '\n';
}

int main() {
    int i;

    citire();
    initcomp();
    sort(sm + 1, sm + m + 1, cmp);
    for (i = 1; nms <= n - 2; i++) {                   // Se vor selecta n-1 muchii.
        if (FindSet(sm[i].inc) != FindSet(sm[i].sf)) { // Extremitatile muchiei curente sunt in componente conexe diferite.
            nms++;                                     // Selectam inca o muchie.
            arbore[nms] = sm[i];                       // Retinem muchia in arbore.
            ca += arbore[nms].cost;                    // Actualizam costul arborelui.
            Union(FindSet(sm[i].inc), FindSet(sm[i].sf));
        }
    }
    rezultat();
}