#include <iostream>
#include <fstream>

#define pinf 1010
#define minf -1010

using namespace std;

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

struct graf{
    int nod, cost;
    graf *urm;
};

graf *a[110], *aux;
int x, y, c, d[110], viz[110], t[110], minn, pminn, n, m, ans;

void prim()
{
    int i, j, minn, pminn;
    for(i=2; i<=n; i++)
    {
        d[i] = pinf;
    }
    d[1] = minf;
    for(i=1; i<=n; i++)
    {
        minn = pinf;
        for(j=1; j<=n; j++)
        {
            if( d[j]<minn && viz[j]==0 )
            {
                minn = d[j];
                pminn = j;
            }
        }
        viz[pminn] = 1;
        aux = a[pminn];
        while( aux != NULL )
        {
            if( d[ aux->nod ] > aux->cost && viz[aux->nod] == 0 )
            {
                d[ aux->nod ] = aux->cost;
                t[ aux->nod ] = pminn;
            }
            aux = aux->urm;
        }
    }
}

int main()
{
    int i;
    fin >> n >> m;
    for(i=1; i<=m; i++)
    {
        fin >> x >> y >> c;
        aux = new graf;
        aux->cost = c;
        aux->nod = x;
        aux->urm = a[y];
        a[y] = aux;

        aux = new graf;
        aux->cost = c;
        aux->nod = y;
        aux->urm = a[x];
        a[x] = aux;
    }
    prim();
    for(i=2; i<=n; i++)
    {
        ans+=d[i];
    }
    fout << ans << '\n';
    fout << n-1 << '\n';
    for(i=2; i<=n; i++)
    {
        fout << i << " " << t[i] << '\n';
    }
    return 0;
}