#include <fstream>
#include <algorithm>

using namespace std;

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

int n, m, rez, tati[200005];
bool ok[200005];
struct muchie
{
    int a, b, cost, nr;
} muchii[200005];

bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

int find(int x) {
    if (x != tati[x]) {
        tati[x] = find(tati[x]);
    }
    return tati[x];
}

void unire(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX != rootY) {
        tati[rootY] = rootX;
    }
}

int main()
{
    int cnt = 0;
    in >> n >> m;

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

    for (int i = 1, a, b, x; i <= m; i++) {
        in >> a >> b >> x;
        muchii[i].a = a;
        muchii[i].b = b;
        muchii[i].nr = i;
        muchii[i].cost = x;
    }

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

    for (int i = 1; i <= m; i++) {
        int tatA = find(muchii[i].a);
        int tatB = find(muchii[i].b);
        if (tatA != tatB) {
            rez += muchii[i].cost;
            ok[muchii[i].nr] = true;
            cnt++;
            unire(tatA, tatB);
        }
    }

    out << rez << '\n';
    out << cnt << '\n';
    for (int i = 1; i <= m; i++)
        if (ok[muchii[i].nr])
            out << muchii[i].a << " " << muchii[i].b << '\n';

    return 0;
}