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

const int kNMax = 200010, kMMax = 400010;
struct muc {int x, y, cost;} muchii[kMMax];
int n, m, sol, tata[kNMax], poz[kNMax];


bool Cmp(muc A, muc B) {
    return A.cost < B.cost;
}

void Citire() {
    ifstream in("apm.in");
    in >> n >> m;
    for (int i = 1; i <= m; ++i)
        in >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
    in.close();
}

int Dfs(int nod) {
    if (nod != tata[nod])
        tata[nod] = Dfs(tata[nod]);
    return tata[nod];
}

void Initializare() {
    sort(muchii + 1, muchii + m + 1, Cmp);
    for (int i = 1; i <= n; ++i)
        tata[i] = i;
}

void Solve() {
    Initializare();
    int nr = 0;
    for (int i = 1; i <= m; ++i) {
        int nod1 = muchii[i].x, nod2 = muchii[i].y, cost = muchii[i].cost;
        if (Dfs(nod1) != Dfs(nod2)) {
            tata[Dfs(nod1)] = Dfs(nod2);
            poz[++nr] = i;
            sol += cost;
        }
    }

}
void Afisare() {
    ofstream out("apm.out");
    out << sol << '\n';
    out << n-1 << '\n';
    for (int i = 1; i <= n - 1 ; ++i)
        out << muchii[poz[i]].x << ' ' << muchii[poz[i]].y << '\n';
    out.close();

}

int main() {
    Citire();
    Solve();
    Afisare();
    return 0;
}