# include <stdio.h>
# define pl 1000
using namespace std;

int x,y,n,m,i,t[200005],h[200005],s;

  struct muchie
  {
	  int x,y,c;
	  muchie *urm;
  }*a[2005],*p,*v,*q;

  int rad (int x)
  {
	  if (t[x]==x)
		  return x;
	  else
		  return rad (t[x]);
  }
  
  void uneste (int x,int y)
  {
	  int xx=rad (x);
	  int yy=rad (y);
	  if (h[xx]<h[yy])
		  t[xx]=yy;
	  else
		  if (h[xx]>h[yy])
			  t[yy]=xx;
		  else
		  {
			  t[xx]=yy;
			  h[yy]++;
		  }
  }
 
int main ()
{
	freopen ("apm.in","w",stdin);
	freopen ("apm.out","r",stdout);
	scanf ("%i%i",&n,&m);;
	for (i=1;i<=m;i++)
	{
		p=new muchie;
		scanf ("%i%i%i",&p->x,&p->y,&p->c);
		p->urm=a[p->c+pl];
		a[p->c+pl]=p;
	}
	for (i=1;i<=n;i++)
	{	
		t[i]=i;
		h[i]=1;
	}
	for (i=0;i<=2000;i++)
	{
		p=a[i];
		while (p)
		{
			if (rad(p->x)!=rad(p->y))
			{	
				s+=p->c;
				q=new muchie;
				q->x=p->x;
				q->y=p->y;
				q->c=p->c;
				q->urm=v;
				v=q;
				
				uneste (p->x,p->y);
			}
		p=p->urm;
		}
	}
	printf ("%i\n%i\n",s,n);
	while (v)
	{
		printf ("%i %i\n",v->x,v->y);
		v=v->urm;
	}
		
		return 0;
}