#include <fstream>
#include <algorithm>

#define NMAX 200005
#define MMAX 400005

using namespace std;

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

int n, m, cost;
int t[NMAX];
int x[MMAX], y[MMAX], c[MMAX], ind[MMAX];
int sol[NMAX];

int cmp(int a, int b)
{
    return c[a] < c[b];
}
int grupa(int i)
{
    if (t[i] == i) return i;
    t[i] = grupa(t[i]);
    return grupa(t[i]);
}
void reuniune(int i, int j)
{
    t[grupa(i)] = grupa(j);
}
int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        fin >> x[i] >> y[i] >> c[i];
        ind[i] = i;
    }
    sort(ind + 1, ind + m + 1, cmp);
    for (int i = 1; i <= n; ++i) t[i] = i;

    int k = 0;
    for (int i = 1; i <= m; ++i)
    {
        if (grupa(x[ind[i]]) != grupa(y[ind[i]]))
        {
            cost += c[ind[i]];
            sol[++k] = ind[i];
            reuniune(x[ind[i]], y[ind[i]]);
        }
    }
    fout << cost << '\n';
    fout << n-1 << '\n';
    for (int i = 1; i < n; ++i)
        fout << x[sol[i]] << ' ' << y[sol[i]] << '\n';
    return 0;
}