#include <fstream>

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



int n,m;
int capm=0,numar=0,v[1000],auxiliar;
struct nod
{
    int x,y,c;
}M[1000],m2[1000];


void cit()
{
    int i;
    fin>>n>>m;


    for(i=1;i<=m;i++)
{
    fin>>M[i].x>>M[i].y>>M[i].c;
    }
}
int poz(int i,int j)
{ int aux,i0,j0;
nod aux2;
i0=0;
j0=-1;

    while(i<j)
    {
        if(M[i].c>M[j].c)

        { aux2=M[i];
          M[i]=M[j];
          M[j]=aux2;
          aux=-i0;
          i0=-j0;
          j0=aux;
        }
        i+=i0;
        j+=j0;
        }return i;
    }

    void quick(int i,int j)
    {
        int k;
        if(i<j)
        {
            k=poz(i,j);
            quick(i,k-1);
            quick(k+1,j);
        }
    }


void unire(int i,int j)
{ int k;
int aux=v[j];
for(k=1;k<=n;k++)
 if(v[k]==aux) v[k]=v[i];
}

void kruskal()
{
    int i;
    for(i=1;i<=n;i++)
    v[i]=i;
    quick(1,m);
    for(i=1;i<=m;i++)
     if(v[M[i].x]!=v[M[i].y])
    {  unire(M[i].x,M[i].y);
       capm+=M[i].c;
       numar++;
       m2[numar]=M[i];
    }
}

int main()
{
cit();
kruskal();
fout<<capm<<endl<<numar<<endl;
int i;
for(i=1;i<=numar;i++)
fout<<m2[i].x<<" "<<m2[i].y<<endl;
    return 0;
}