#include <cstdio>
using namespace std;
int t,st[2001],sf[2001];
int next[400001],dest1[400001],dest2[400001],fin[400001];
int father[200001],rang[200001];
int n,m,c,x,y,i,j,l;
void add(int c,int x, int y)
{
    t++;
    if(st[c]==0){st[c]=t;}
    else{next[sf[c]]=t;}
    sf[c]=t;
    next[t]=0;
    dest1[t]=x;
    dest2[t]=y;
}
int query(int nod)
{
    if(father[nod]==nod){return nod;}
    else{
        father[nod]=query(father[nod]);
        rang[nod]=rang[father[nod]]+1;
        return father[nod];
        }
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){father[i]=i;}
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        c=c+1000;
        add(c,x,y);
    }
    c=0;l=n-1;
    for(i=0;(i<=2000)&&l;i++)
    {
        for(j=st[i];j&&l;j=next[j])
        {
            x=dest1[j];y=dest2[j];
            x=query(x);y=query(y);
            if(x!=y)
            {
                c+=i-1000;l--;
                fin[j]=1;
                if(rang[x]>rang[y]){father[y]=x;rang[y]++;}
                else{father[x]=y;rang[x]++;}
            }
        }
    }
    printf("%d\n%d\n",c,n-1);
    for(i=0;i<=2000;i++)
    {
        for(j=st[i];j;j=next[j])
        {
            if(fin[j])
            {
                printf("%d %d\n",dest1[j],dest2[j],n-1);
            }
        }
    }
return 0;
}