#include <fstream>
#include <algorithm>
#define DMAX 100
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct muchie {int x, y, val;};

void citire();
bool compara(muchie a, muchie b)
{return a.val<b.val;}
void rez();
void afisare();

int n, m;
muchie graf[DMAX];
int cc[DMAX];

muchie sol[DMAX];
int nrsol, s;

int main()
{
    citire();
    sort(graf+1, graf+m+1, compara);
    rez();
    afisare();
    
    fin.close();
    fout.close();
    return 0;
}

void citire()
{
    int i;
    
    fin>> n>> m;
    for (i=1; i<=m; i++)
    {
        fin >> graf[i].x;
        fin >> graf[i].y;
        fin >> graf[i].val;
    }
}

void rez()
{
    int i, j;
    int val;
    
    for (i=1; i<=n; i++) cc[i]=i;
    
    for (i=1; i<=m; i++)
        if (cc[graf[i].x]!=cc[graf[i].y])
        {
            //fout<< graf[i].x<< ' '<< graf[i].y<< '\n';
            sol[++nrsol]=graf[i];
            s+=graf[i].val;
            
            if (cc[graf[i].x]<cc[graf[i].y])
            {
                val=cc[graf[i].y];
                for (j=1; j<=n; j++)
                    if (cc[j] == val)
                        cc[j] = cc[graf[i].x];
            }
            else
            {
                val=cc[graf[i].x];
                for (j=1; j<=n; j++)
                    if (cc[j] == val)
                        cc[j] = cc[graf[i].y];
            }
        }
}

void afisare()
{
    int i;
    
    fout<< s<< '\n';
    fout<< nrsol<< '\n';
    for (i=1; i<=nrsol; i++)
        fout<< sol[i].x<< ' '<< sol[i].y<< '\n';
}