#include <algorithm>
#include <fstream>
using namespace std;
	
ifstream fin("apm.in");
ofstream fout("apm.out");
	
const int nmax = 200000;
const int mmax = 400000;

int n, m, cost, t;
struct str {
    int x, y, c;
};
	
int r[nmax + 1], cost_total[nmax + 1];
str edge[mmax + 1];
	
bool cmp(str x, str y) {
    return x.c < y.c;
}

int root(int x) {
    if (x != r[x]) {
        return r[x] = root(r[x]);
    }
    return x;
}
int main() {
    fin>> n >> m;
    for (int i = 1; i <= m; ++i) {
        fin>> edge[i].x >> edge[i].y >> edge[i].c;
    }
    sort(edge + 1, edge + m + 1, cmp);
    for (int i = 1; i <= n; ++i) {
        r[i]= i;
    }
    for (int i = 1; i <= m; ++i) {
        int rx = root(edge[i].x), ry = root(edge[i].y);
        if (rx != ry) {
            cost += edge[i].c;
            r[ry] = rx;
            cost_total[++t] = i;
        }
    }
    fout << cost << "\n" << t << "\n";
    for ( int i = 1; i <= t; ++i ) {
        fout << edge[cost_total[i]].x <<" "<< edge[cost_total[i]].y << "\n";
    }
    return 0;
}