#include <algorithm>
#include <fstream>
#define NMAX 200002
#define MMAX 400002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, nrsel, cc[NMAX], a[NMAX], costmin;
struct muchie { int x, y, c; };
muchie G[MMAX];
bool compar(muchie a, muchie b) { return a.c < b.c; };
int main()
{   
    int i, j, minim, maxim;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
        fin >> G[i].x >> G[i].y >> G[i].c;
    sort(G + 1, G + m + 1, compar);
    for (i = 1; i <= n; i++) cc[i] = i;
    i = 1;
    while (nrsel<n-1)
    {
        if (cc[G[i].x] != cc[G[i].y])
        {
            costmin += G[i].c;
            ++nrsel;
            a[nrsel] = i;
            minim = cc[G[i].x]; maxim = cc[G[i].y];
            if (minim > maxim) { minim = cc[G[i].y]; maxim = cc[G[i].x]; }
            for (j = 1; j <= n; j++)
                if (cc[j] == maxim)
                    cc[j] = minim;
        }
        i++;
    }
    fout << costmin << '\n'<<n-1<<'\n';
    for (i = 1; i < n; i++)
        fout << G[a[i]].x << ' ' << G[a[i]].y << '\n';
    return 0;
}