/// kruskal, algoritmul de apm prin selectie de muchii
/// se sorteaza crescator dupa cost muchiile, si se fac
/// n-1 alegeri de muchii, in ordine crescatoare a costurilor
/// si la fiecare pas muchia aleaza sa aiba extremitatile
/// in componente conexe diferite, dupa alegere, componentele
/// conexe ale muchiei alese unindu-se
/// timp de executare: m log m (sortarea muchiilor)
/// + m * log n
#include <fstream>
#include <algorithm>
#define DIMM 400010
#define DIMN 200010
using namespace std;

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

muchie v[DIMM];
int t[DIMN], s[DIMN];

int n, m, k, i, sol;

int cmp(const muchie &a, const muchie &b) {
    return a.cost < b.cost;
}

int getRad(int x) {
    int y = x, aux;

    while (t[x] > 0)
        x = t[x];

    while (t[y] > 0) {
        aux = t[y];
        t[y] = x;
        y = aux;
    }

    return x;
}

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

    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>v[i].x>>v[i].y>>v[i].cost;
    }
    /// sortez muchiile dupa cost
    sort(v+1, v+m+1, cmp);

    /// consider ca fiecare nod este o componenta conexa diferita
    for (i=1;i<=n;i++)
        t[i] = -1;


    /// parcurg muchiile in ordine crescatoare a costului.
    for (i=1;i<=m;i++) {
        /// as vrea sa aleg muchia i
        int rx = getRad(v[i].x);
        int ry = getRad(v[i].y);
        if (rx != ry) {
            s[++k] = i;
            sol += v[i].cost;

            if (t[ rx ] < t[ ry ]) {
                /// rx este radacina arborelui cu mai multe noduri
                t[rx] += t[ry];
                t[ry] = rx;
            } else {
                t[ry] += t[rx];
                t[rx] = ry;
            }

        }
    }
    fout<<sol<<"\n"<<n-1<<"\n";
    for (i=1;i<n;i++)
        fout<<v[ s[i] ].x<<" "<<v[ s[i] ].y<<"\n";
    return 0;
}