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

struct M {
    int x, y, c;
};

int t[200001];
M v[400001];

int rad(int x) {
    if (t[x] == x) return x;
    t[x] = rad(t[x]);
    return t[x];
}

void unire(int a, int b) {
    t[rad(a)] = rad(b);
}
bool cmp(M a, M b) {
    return a.c < b.c;
}


int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");

    int n, m;
    f >> n >> m;

    for (int i = 1; i <= m; i++)
        f >> v[i].x >> v[i].y >> v[i].c;

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

    for (int i = 1; i <= n; i++)
        t[i] = i;

    long long s = 0;
    int nr = 0;
    M sol[200001];

    for (int i = 1; i <= m && nr < n - 1; i++) {
        int a = v[i].x, b = v[i].y;
        if (rad(a) != rad(b)) {
            unire(a, b);
            s += v[i].c;
            sol[++nr] = v[i];
        }
    }

    g << s << "\n" << nr << "\n";
    for (int i = 1; i <= nr; i++)
        g << sol[i].x << " " << sol[i].y << "\n";

    return 0;
}