#include <fstream>
FILE*f;
FILE*g;
using namespace std;
#define maxn 200050
struct nod{int x;int y;int z;}c[100];
int i,j,k,l,m,n,x,y,z,v[100],v1[100],v2[100],s,k1,al;
int main()
{f=fopen("apm.in","r");
g=fopen("apm.out","w");
fscanf(f,"%d%d",&m,&n);
k=1;
fscanf(f,"%d%d%d",&x,&y,&z);
    c[1].x=x;
    c[1].y=y;
    c[1].z=z;
for(i=1;i<=n;i++)
{
    k++;
    fscanf(f,"%d%d%d",&x,&y,&z);
    l=k;
    while(c[l-1].z>=z)
    {
        c[l].z=c[l-1].z;
        c[l].x=c[l-1].x;
        c[l].y=c[l-1].y;
        l--;
        if(l-1==0)
        break;
    }
    c[l].x=x;
    c[l].y=y;
    c[l].z=z;
}
    for(i=1;i<=m;i++)
        v[i]=i;
    for(i=1;i<=k;i++)
    {
        if(v[c[i].x]!=v[c[i].y])
        {al=v[c[i].y];
            for(j=1;j<=m;j++)
                if(v[j]==al)
                v[j]=v[c[i].x];
            s+=c[i].z;
            k1++;
        v1[k1]=c[i].x;
        v2[k1]=c[i].y;
        }
        if(k1==(n-1))
            break;

    }
fprintf(g,"%d\n%d",s,k1);
for(i=1;i<=k1;i++)
    fprintf(g,"\n%d %d ",v1[i],v2[i]);










return 0;
}