#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 200000;
const int MMAX = 400000;

struct muchie {
    int x, y, c;
};
muchie a[NMAX+1];
int h[NMAX+1], d[NMAX+1];

bool cmp (muchie p, muchie q) {
    return p.c < q.c;
}

void Union(int x, int y) {
    if (h[x] > h[y]) {
        d[y] = x;
    } else {
        d[x] = y;
        if (h[x] == h[y]) ++h[y];
    }
}

int Find(int x) {
    int r = x;
    while (r != d[r]) r = d[r];
    int y = x, t;
    while (y != r) {
        t = d[y];
        d[y] = r;
        y = t;
    }
    return r;
}



int main() {
    int n, m;
    ifstream f("apm.in");
    ofstream g("apm.out");
    f >> n >> m;

    for (int i = 1; i <= n; ++i) {
        h[i] = 1;
        d[i] = i;
    }
//    cout << n << " " << m << endl;
    for (int i = 1; i <= m; ++i) {
        f >> a[i].x >> a[i].y >> a[i].c;
//        cout << a[i].x << " " << a[i].y << " " << a[i].c << endl;
    }

    sort(a+1, a+m+1, cmp);
    vector<muchie> sol;
    int s = 0;
    for (int i = 1; i <= m; ++i) {
        int p = Find(a[i].x);
        int q = Find(a[i].y);
//        cout << "p, q " << p << " " << q << endl;
        if (p != q) {
            s = s + a[i].c;
            sol.push_back(a[i]);
            Union(p, q);
        }
    }


    g << s << "\n";
    g << n-1 << '\n';
    for (int i = 0; i < n-1; ++i) {
        g << sol[i].y << " " << sol[i].x << endl;
    }

    return 0;
}