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

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

const int MAXN = 200005;
const int MAXM = 400005;

int n, m;
struct mch {
    int a;
    int b;
    int c;
} v[MAXN];

bool srt(mch a, mch b) {
    return a.c < b.c;
}

int p[MAXN], r[MAXN];

int parent(int k) {
    int t = k;
    while (t != p[t]) {
        t = p[t];
    }
    while (k != p[k]) {
        int y = p[k];
        p[k] = t;
        k = y;
    }
    return t;
}

long long s;
vector<pair<int, int>> sol;

int main() {

    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> v[i].a >> v[i].b >> v[i].c;
    }

    for (int i = 1; i <= n; ++i) {
        p[i] = i;
        r[i] = 1;
    }

    sort(v + 1, v + m + 1, srt);

    for (int i = 1; i <= m; ++i) {
        int a = v[i].a;
        int b = v[i].b;
        int c = v[i].c;
        if (parent(a) != parent(b)) {
            s += (long long)c;
            sol.push_back({a, b});
            a = parent(a);
            b = parent(b);
            if (r[a] < r[b]) {
                p[a] = b;
                r[b]++;
            }
            else {
                p[b] = a;
                r[a]++;
            }
        }
    }

    fout << s << '\n';
    fout << sol.size() << '\n';
    for (int i = 0; i < sol.size(); ++i) {
        fout << sol[i].first << ' ' << sol[i].second << '\n';
    }

    fout.close();
    return 0;
}