#include <fstream>
#include <algorithm>

using namespace std;

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

int n, m, rez, tati[5001];
bool ok[5001];
struct muchie
{
    int a, b, cost, nr;
} muchii[5001];

bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}
int main()
{
    in >> n >> m;
    for (int i = 1, a, b, x; i <= m; i++){
        in >> a >> b >> x;
        muchii[i].a = a;
        muchii[i].b = b;
        muchii[i].nr = i;
        muchii[i].cost = x;
        tati[i] = i;
    }
    sort(muchii + 1, muchii + m + 1, cmp);

    for (auto muchie : muchii)
        if (tati[muchie.a] != tati[muchie.b])
        {
            rez += muchie.cost;
            ok[muchie.nr] = 1;
            int old = tati[muchie.a], nou = tati[muchie.b];
            for (int i = 1; i <= n; i++)
                if (tati[i] == old)
                    tati[i] = nou;
        }

    out << rez << '\n';
    int cnt = 0;
    for (int i = 1; i <= m; i++)
        if (ok[muchii[i].nr]) cnt ++;
    out << cnt << '\n';
    for (int i = 1; i <= m; i++)
        if (ok[muchii[i].nr])
            out << muchii[i].a << " " << muchii[i].b << '\n';

    return 0;
}