#include <fstream>
#include <algorithm>
#define NMAX 400001

using namespace std;

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

int n, m, total, nrRez;
int tati[NMAX], rang[NMAX];
pair<int, int> rez[NMAX];
struct muchie {
    int x, y, cost;
} g[NMAX];

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

void citire() {
    int i;

    fin >> n >> m;
    for (i = 1; i <= m; i++)
        fin >> g[i].x >> g[i].y >> g[i].cost;
    sort(g + 1, g + m + 1, compara);
    for (i = 1; i <= n; i++) {
        tati[i] = i;
        rang[i] = 1;
    }
}

int gasesteTati(int nod) {
    while (tati[nod] != nod)
        nod = tati[nod];
    return nod;
}

void unesteMuchii(int x, int y) {
    if (rang[x] < rang[y])
        tati[x] = y;
    else if (rang[x] > rang[y])
        tati[y] = x;
    else {
        tati[x] = y;
        rang[y]++;
    }
}

void kruskal() {
    int i, tataX, tataY;

    for (i = 1; i <= m; i++) {
        tataX = gasesteTati(g[i].x);
        tataY = gasesteTati(g[i].y);
        if (tataX != tataY) {
            unesteMuchii(tataX , tataY);
            rez[++nrRez] = make_pair(g[i].x, g[i]. y);
            total += g[i].cost;
        }
    }
}

void afisare() {
    int i;

    fout << total << '\n' << n - 1 << '\n';
    for (i = 1; i <= nrRez; i++)
        fout << rez[i].first << ' ' << rez[i].second << '\n';
}

int main() {
    citire();
    kruskal();
    afisare();

    fin.close();
    fout.close();

    return 0;
}