#include <fstream>
#include <vector>

#include <algorithm>

#define MAXN 200005
#define MAXM 400005

using namespace std;

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

int N, M, dad[MAXN], s;

struct str{
    int x, y, c;

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

str muchie[MAXM];
vector <str> sol;

void Read() {
    fin >> N >> M;

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

    sort(muchie + 1, muchie + M + 1);
}

inline int father(int node) {
    if (node != dad[node]) {
        dad[node] = father(dad[node]);
    }
    return dad[node];
}

inline void APM() {
    int v1, v2;

    for (int i = 1; i <= N; i++)
        dad[i] = i;

    for (int i = 1; i <= M; i++) {
        v1 = father(muchie[i].x);
        v2 = father(muchie[i].y);

        if (v1 != v2) {
            dad[v1] = v2; s += muchie[i].c;
            sol.push_back({muchie[i].x, muchie[i].y, 0});

            if (sol.size() == N - 1)
                return;
        }
    }
}

inline void Afisare() {
    fout << s << "\n" << N - 1 << "\n";

    for (auto x : sol)
        fout << x.x << " " << x.y << "\n";
}

int main () {
    Read();
    APM();
    Afisare();

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