#include <bits/stdc++.h>

using namespace std;


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

struct Muchie {
    int x;
    int y;
    int c;
};

int n, m, i, j, tmp1, tmp2, tmp3;
vector<Muchie> muchii;
vector<Muchie> result;
vector<int> tati;

ostream &operator<<(ostream &out, vector<Muchie> v) {
    for (auto x: v) {
        out << x.x << " " << x.y << "\n";
    }
//    out << "\n";

    return out;
}

inline int getRoot(int nod) {
    if (tati[nod] == nod)
        return nod;


    return getRoot(tati[nod]);
}

int main() {
    fin >> n >> m;

    muchii.resize(m);

    tati.resize(n);
    for (i = 0; i < n; ++i) {
        tati[i] = i;
    }


    for (i = 0; i < m; ++i) {
        fin >> muchii[i].x >> muchii[i].y >> muchii[i].c;
    }

    sort(muchii.begin(), muchii.end(), [&](Muchie a, Muchie b) -> bool { return a.c < b.c; });

    for (i = 0; i < m; ++i) {
        if (getRoot(muchii[i].x) != getRoot(muchii[i].y)) {
            result.push_back(muchii[i]);
            tati[getRoot(muchii[i].y)] = getRoot(muchii[i].x);
        }
    }

    int costTotal = accumulate(result.begin(), result.end(), 0,
                               [](int sum, const Muchie &curr) { return sum + curr.x; });

    fout << costTotal << "\n";
    fout << result.size() << "\n";
    fout << result;


    return 0;
}