#include <fstream>
#define NM 20001
#define INF 1001

using namespace std;

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

int c[NM][NM], viz[NM], t[NM], d[NM];
int n, m, x, y, cost, nr, dm, im, ct, i, j;

int main() {
    fin >> n >> m;
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            c[i][j] = c[j][i] = INF;

    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        c[x][y] = c[y][x] = cost;
    }

    for (int i = 2; i <= n; i++)
    {
        d[i] = c[1][i];
        t[i] = 1;
    }

    viz[1] = 1;
    nr = 1;
    ct = 0;

    while (nr < n)
    {
        dm = INF;
        for (i = 2; i <= n; i++)
            if (viz[i] == 0 && d[i] < dm)
            {
                dm = d[i];
                im = i;
            }

        nr++;
        viz[im] = 1;
        ct = ct + d[im];

        for (i = 2; i <= n; i++)
            if (viz[i] == 0 && d[i] > c[im][i])
            {
                d[i] = c[im][i];
                t[i] = im;
            }
    }

    fout << ct << '\n';
    fout << n - 1 << '\n';
    for (i = 2; i <= n; i++)
        fout << i << ' ' << t[i] << '\n';

}