#include<fstream>
#include<algorithm>
#include<vector>
#define N 400005
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n, m, i, j, s;
struct apm {
    int x, y, c;
};
apm a[N];
int gr[N];
vector<int> res;
bool cmp (apm o, apm p) {
    return o.c < p.c;
}
int grupa(int i) {
    if (gr[i] == 0) return i;
    gr[i] = grupa(gr[i]);
    return gr[i];
}
void unire(int i, int j) {
    gr[grupa(i)] = grupa(j);
}
int main() {
    cin >> n >> m;
    for (i = 1; i <= m; i++) cin >> a[i].x >> a[i].y >> a[i].c;
    sort(a + 1, a + m + 1, cmp);
    for (i = 1; i <= m; i++) {
        if (grupa(a[i].x) != grupa(a[i].y)) {
            s += a[i].c;
            unire(a[i].x, a[i].y);
            res.push_back(i);
        }
    }
    cout << s << '\n';
    cout << n - 1 << '\n';
    for (i = 0; i < res.size(); i++) {
        cout << a[res[i]].x << ' ' << a[res[i]].y << '\n';
    }
    return 0;
}