#include<bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

const int Nmax = 200005;
const int Mmax = 400005;

struct muchie {

    int nod1, nod2, cost;
} M[Mmax], sol[Mmax];

bool cmp(muchie a, muchie b) {

    return a.cost < b.cost;
}

int nivel[Nmax], tata[Nmax], cost_min, n, m, k, i, r1, r2, ii;

void citire() {

    f >> n >> m;

    for(i = 1; i <= m; ++i)
        f >> M[i].nod1 >> M[i].nod2 >> M[i].cost;

    sort(M + 1, M + m + 1, cmp);
}

int radacina(int nod) {

    int rad, aux;

    for(rad = nod; rad != tata[rad]; rad = tata[rad]);

    while(nod != tata[nod]) {

        aux = tata[nod];

        tata[nod] = rad;

        nod = aux;
    }

    return rad;
}

void unire(int n1, int n2) {

    if(nivel[n1] > nivel[n2])
        tata[n2] = n1;
    else
        tata[n1] = n2;

    if(nivel[n1] == nivel[n2])
        nivel[n1]++;
}

void Kruskal() {

    for(i = 1; i <= n; ++i)
        tata[i] = i, nivel[i] = 1;

    i = 1;

    for(ii = 1; ii <= n - 1;) {

        r1 = radacina(M[i].nod1);
        r2 = radacina(M[i].nod2);

        if(r1 != r2){

            ++k;
            sol[k].nod1 = M[i].nod1;
            sol[k].nod2 = M[i].nod2;

            cost_min += M[i].cost;

            unire(r1, r2);

            ++ii;
        }

        ++i;
    }
}

void afisare() {

    g << cost_min << '\n' << k << '\n';

    for(i = 1; i <= k; ++i)
        g << sol[i].nod1 << ' ' << sol[i].nod2 << '\n';
}

int main() {

    citire();
    Kruskal();
    afisare();

    return 0;
}