#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define pb push_back

struct data {
   int c, x, y;
}g[500001];

int r[500001], sol[500001][3], n, m, p, cost, muchii;

int grupa(int i) {
    if(r[i] == i) return i;
    r[i] = grupa(r[i]);
    return r[i];
}

void reuniune(int i, int j) {
    r[grupa(i)] = grupa(j);
}

inline bool cmp(data a, data b) {
    return a.c < b.c;
}

int main() {
    int i, x, y, c;
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin >> n >> m;
    for(i = 1; i <= m; ++i) {
        fin >> x >> y >> c;
        g[++p] = data{c, x, y};
    }

    sort(g + 1, g + m + 1, cmp);

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

    for(i = 1, p = 0; i <= m; ++i) {
        if(grupa(g[i].x) != grupa(g[i].y)) {
            reuniune(g[i].x, g[i].y);
            cost += g[i].c; ++muchii;
            sol[++p][1] = g[i].x; sol[p][2] = g[i].y;
        }
    }

    fout << cost << '\n' << muchii << '\n';
    for(i = 1; i <= p; ++i)
        fout << sol[i][1] << ' ' << sol[i][2] << '\n';

    fout.close();
    return 0;
}