#include<fstream>
#include<algorithm>
#include<vector>

#define Nmax 400010

using namespace std;

int a, b, i, n, m, x[Nmax], y[Nmax], t[Nmax], cost[Nmax], par[Nmax], sol;
vector <int> solutie;

int find(int r)
{
    if (par[r] == r)
        return r;

    par[r] = find(par[r]);

    return par[r];
}

void unite(int a, int b)
{
    if (a == b)
        return;

    par[a] = b;
}

int cmp (int i, int j)
{
    if (cost[i] > cost[j])
        return 0;
    return 1;
}

int main()
{
    ifstream f("apm.in");
    ofstream h("apm.out");
    f >> n >> m;
    for (i = 1; i <= m; ++i)
    {
        f >> x[i] >> y[i] >> cost[i];
        t[i] = i;
    }
    sort (t + 1, t + m + 1, cmp);
    for (i = 1; i <= n; ++i)
        par[i] = i;
    for (i = 1; i <= m; ++i)
        if (find(x[t[i]]) != find(y[t[i]]))
        {
            sol += cost[t[i]];
            unite (find(x[t[i]]), find(y[t[i]]));
            solutie.push_back(t[i]);
        }
    h << sol << '\n' << n - 1 << '\n';
    for (i = 0; i < n - 1; ++i)
        h << x[solutie[i]] << " " << y[solutie[i]] << '\n';
    f.close();
    h.close();
    return 0;
}