#include <fstream>
#include <algorithm>

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

const int nMax = 2e5 + 1;

struct muchie {
    int x, y, cost;
}v[nMax], muchii[nMax];

int n, m;

int tata[nMax], rang[nMax];

int father (int x) {
    if (tata[x] == 0)
        return x;
    else {
        int root = father (tata[x]);
        tata[x] = root;
        return root;
    }
}

void unite (int a, int b) {
    int fathera = father (a);
    int fatherb = father (b);
    if (rang[fathera] > rang[fatherb])
        tata[fatherb] = fathera;
    else {
        tata[fathera] = fatherb;
        if (rang[fathera] == rang[fatherb])
            rang[fatherb] += 1;
    }
}

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

int main () {
    fin >> n >> m;
    for (int i = 1; i <= n; i += 1) rang[i] = 1;
    for (int i = 1; i <= m; i += 1)
        fin >> v[i].x >> v[i].y >> v[i].cost;


    std::sort (v + 1, v + 1 + m, cond);


    int used = 0, total = 0;
    for (int i = 1; i <= m && used != n - 1; i += 1)
        if (father (v[i].x) != father (v[i].y)) {
            unite (v[i].x, v[i].y), used += 1, total += v[i].cost;
            muchii[used].x = v[i].x, muchii[used].y = v[i].y;
        }


    fout << total << '\n' << used << '\n';
    for (int i = 1; i <= used; i += 1)
        fout << muchii[i].x << ' ' << muchii[i].y << '\n';
    return 0;
}