# include <fstream>
# define pl 1000
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
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 ()
{
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		p=new muchie;
		f>>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;
		}
	}
	g<<s<<"\n"<<n-1<<"\n";
	while (v)
	{
		g<<v->x<<" "<<v->y<<"\n";
		v=v->urm;
	}
		
		return 0;
}