#include <fstream>
#include <algorithm>
#define NMAX 2010

using namespace std;

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

int n,C[NMAX],m,Cost;
int minim,maxim;
int cati_de1=1;

struct elem{int x; int y; int cost;} muchie[NMAX],retin[NMAX];

int comp(elem a, elem b)
{
    if(a.cost<b.cost) return 1;
    if(a.cost==b.cost && a.x<b.x) return 1;
    if(a.cost==b.cost && a.x==b.x && a.y<b.y) return 1;
    return 0;
}

int main()
{
    int i,j,z=0;
    fin >> n >> m;
    for(i=1;i<=m;i++)
    {
        fin >> muchie[i].x;
        fin >> muchie[i].y;
        fin >> muchie[i].cost;
        C[i]=i;
    }
    sort(muchie+1,muchie+m+1,comp);
    while(cati_de1!=n)
    {
        for(i=1;i<=m;i++)
            if(C[muchie[i].x]!=C[muchie[i].y])
            {
                if(C[muchie[i].x]<C[muchie[i].y])
                    minim=C[muchie[i].x],maxim=C[muchie[i].y];
                else minim=C[muchie[i].y],maxim=C[muchie[i].x];
                for(j=1;j<=n;j++)
                    if(C[j]==maxim)
                    {
                        C[j]=minim;
                        if(minim==1)
                            cati_de1++;
                        z++;
                        retin[z]=muchie[i];
                    }
                 Cost+=muchie[i].cost;
            }
    }
    fout << Cost << '\n';
    fout << n-1 << '\n';
    for(i=1;i<n;i++)
        fout << retin[i].x << ' ' << retin[i].y  << ' ' << retin[i].cost<< '\n';
    return 0;
}