#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];
			if(query(x)!=query(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;
}