#include <fstream>
#include <algorithm>

#define MAXN 200002

using namespace std;

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

struct str{
    int x, y, cost;

    bool operator <(const str& other) const{
        return cost < other.cost;
    }
};

str muchie[MAXN * 2];

int n, m, p[MAXN], p1, p2, sol[MAXN];

inline void Read() {
    fin >> n >> m;

    for (int i = 1; i <= m; i++) {
        fin >> muchie[i].x >> muchie[i].y >> muchie[i].cost;
    }

    sort(muchie + 1, muchie + m + 1);

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

inline int parinte(int nod) {
    if (p[nod] == nod) return nod;
    return p[nod] = parinte(p[nod]);
}

inline void apm() {
    int nn = 0; int suma = 0;

    for (int i = 1; i <= m; i++) {
        p1 = parinte(muchie[i].x);
        p2 = parinte(muchie[i].y);

        if (p1 != p2) {
            p[p1] = p2;

            suma += muchie[i].cost;
            sol[++nn] = i;

            if (nn == n - 1)
                break;
        }
    }

    fout << suma << "\n" << nn << "\n";

    for (int i = 1; i <= nn; i++)
        fout << muchie[sol[i]].x << " " << muchie[sol[i]].y << "\n";
}

int main () {
    Read();
    apm();

    fin.close(); fout.close(); return 0;
}