#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int mmax = 400005;
const int nmax = 200005;
struct edge {
    int x, y, c;
}v[mmax];

int tt[nmax], n, m, x, y, c, cost, nr, sol[nmax], i;

int update(int x) {
    int r = x, y;

    while (tt[r] != r)
        r = tt[r];

    while (tt[x] != x) {
        y = tt[x];
        tt[x] = r;
        x = y;
    }

    return r;
}

bool cmp(const edge &a, const edge &b) {
    return a.c < b.c;
}

int main() {
    f >> n >> m;
    for (i = 1; i <= m; i++) {
        f >> x >> y >> c;
        v[i] = {x,y,c};
    }

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

    sort(v+1, v+m+1, cmp);
    for (i = 1; i <= m; i++) {
        int X = update(v[i].x), Y = update(v[i].y);

        if (X != Y) {
            tt[X] = Y;
            cost += v[i].c;
            sol[++nr] = i;
        }
    }
    g << cost << '\n' << n-1 << '\n';
    for (i = 1; i < n; i++)
        g << v[sol[i]].x << ' ' << v[sol[i]].y << '\n';
    return 0;
}