#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;
int v[MAXN], r[MAXN];

struct muchie {
    int a;
    int b;
    int c;
} p[MAXM];

vector<muchie> sol;

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

int find(int k) {
    if (v[k] != k) {
        v[k] = find(v[k]);
    }
    return v[k];
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (r[a] > r[b]) {
        v[b] = a;
    }
    else if (r[a] < r[b]) {
        v[a] = b;
    }
    else {
        v[b] = a;
        r[a]++;
    }
}

int main() {

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

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

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

    int s = 0;
    for (int i = 1; i <= m; ++i) {
        if (find(p[i].a) != find(p[i].b)) {
            s += p[i].c;
            unite(p[i].a, p[i].b);
            sol.push_back(p[i]);
        }
    }

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

    fout.close();
    return 0;
}