# include <fstream.h>
ifstream f ("apm.in");
ofstream g ("apm.out");
int a[3000],i,n,m,q,w,e,s[200005],cost,kk,k2;


  struct nod 
  {
	  int info;
	  nod *urm;
  }*x[3000],*y[3000],*p,*v,*z[200005];
  

  void df (int x)
  {
	  nod *p;
	  s[x]=kk;
	  p=z[x];
	  while (p)
	  {   
		  if (s[p->info]==k2)
		  df (p->info);
		  p=p->urm;
	  }
  }
	  
  
  void df2 (int x)
  {
	  nod *p;
	  s[x]=0;
	  p=z[x];
	  
	  while (p)
	  {
		  if (s[p->info]==kk)
		  {
		  g<<x<<" "<<p->info<<"\n";
		  df2(p->info);
		  }
		  p=p->urm;
	  }
  }


int main ()
{
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>q>>w>>e;
		a[e+1000]++;
		p=new nod;
		p->info=q;
		p->urm=x[e+1000];
		x[e+1000]=p;
		p=new nod;
		p->info=w;
		p->urm=y[e+1000];
		y[e+1000]=p;
	}
	
	for (i=1;i<=2000;i++)
	
		if (a[i]!=0)
		
			while (x[i])
			{
			   q=x[i]->info;
			   w=y[i]->info;
			   if (s[q]!=s[w])
			   {
				   cost=cost+i-1000;
				   if (s[q]==0)
					   s[q]=q;
				   kk=s[q];
				   k2=s[w];
				   df (w);
				   
				   
				   p=new nod;
				   p->info=q;
				   p->urm=z[w];
				   z[w]=p;
				   
				   p=new nod;
				   p->info=w;
				   p->urm=z[q];
				   z[q]=p;
			   }
			   else
				   if (s[q]==0 && s[w]==0)
				   {
				   cost=cost+i-1000;
				   
				   s[q]=q;
				   
				   s[w]=q;
				   p=new nod;
				   p->info=q;
				   p->urm=z[w];
				   z[w]=p;
				   p=new nod;
				   p->info=w;
				   p->urm=z[q];
				   z[q]=p;
			   }
					   
					   
			x[i]=x[i]->urm;
			y[i]=y[i]->urm;
			}
	
	g<<cost<<"\n"<<n-1<<"\n";
	kk=s[1];
	df2 (1);
	return 0;
}