#include <stdio.h>
#include <stdlib.h>


struct node  
{
   int nd,v;
};

struct list 
{
	int x,v;
	list * next;
};

int pair[200009],pos[200009],n,m,i,_n,x,y,z;
long long s;
node h[200009],aux;

char use[200009];

list * g[200009],* _aux;

void add(list ** l,int k,int v)
{
  _aux=(list *) malloc(sizeof(list));
  _aux->next=*l;
  _aux->x=k;
  _aux->v=v;
  *l=_aux;
}

const int buff_size=4096;
char buff[buff_size];
int _i=buff_size;


int next_int(FILE * in)
{
    char x,y,k=1;
    int z=0;
   
   if (_i==buff_size)
    y=fread(buff,buff_size,1,in),_i=0;
      
     x=1;
 
      while ((x<48 || x> 57) && x!='-')
         {  
          x=buff[_i];
          _i++;
          if (_i==buff_size)
             {
              y=fread(buff,buff_size,1,in);
              _i=0;
             }
         }
 
      while (x>=48 && x<=57 || x=='-')
      {
        if (x=='-') 
          k=-1; else 
        z=(z<<1)+(z<<3)+x-48;
        x=buff[_i];
        _i++;
         if (_i==buff_size)
           {
               y=fread(buff,buff_size,1,in);
               _i=0;
             }
      }
 
    return z*k;
}


void init()
{
	h[1].nd=1;
	h[1].v=0;
	pos[1]=1;
	pair[1]=-1;
	_n=n;
	for (i=2;i<=n;++i)
		h[i].nd=i,pos[i]=i,h[i].v=200000000,pair[i]=-1;
}

void update(int v,int x)
{
	int fiu=v;
	h[v].v=x;
	while (fiu>>1>0)
	{
		if (h[fiu].v<h[fiu>>1].v)
		{
		   aux.nd=pos[h[fiu].nd];
		   pos[h[fiu].nd]=pos[h[fiu>>1].nd];
		   pos[h[fiu>>1].nd]=aux.nd;
           aux=h[fiu];
           h[fiu]=h[fiu>>1];
           h[fiu>>1]=aux;
		}
		fiu>>=1;
	}
}

void _delete()
{
	int tata=1,fiu=2;

    h[1]=h[_n--];
    pos[h[1].nd]=1;

	while (fiu<=_n)
	{
         if (fiu+1<=_n)
         {
         	if (h[fiu].v<h[fiu+1].v )
         	{
         	  if (h[fiu].v<h[tata].v)
	           {   
	               aux.nd=pos[h[fiu].nd];
				   pos[h[fiu].nd]=pos[h[tata].nd];
				   pos[h[tata].nd]=aux.nd;
		           aux=h[fiu];
		           h[fiu]=h[tata];
		           h[tata]=aux;
	           }
         	} else 
         	 {
         	 	if (h[fiu+1].v<h[tata].v)
         	   {	
	         	   aux.nd=pos[h[fiu+1].nd];
				   pos[h[fiu+1].nd]=pos[h[tata].nd];
				   pos[h[tata].nd]=aux.nd;
		           aux=h[fiu+1];
		           h[fiu+1]=h[tata];
		           h[tata]=aux;
	           fiu++;
	           }
         	 }
         } else 
         {
         	if (h[fiu].v<h[tata].v)
         	{
         	   aux.nd=pos[h[fiu].nd];
			   pos[h[fiu].nd]=pos[h[tata].nd];
			   pos[h[tata].nd]=aux.nd;
	           aux=h[fiu];
	           h[fiu]=h[tata];
	           h[tata]=aux;
         	}
         }

         tata=fiu;
         fiu<<=1;
	}
}


int main(int argc, char const *argv[])
{

	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
  
      n=next_int(stdin);
      m=next_int(stdin);

      init();

      while (m--)
      {
      	x=next_int(stdin);
      	y=next_int(stdin);
      	z=next_int(stdin);
      	add(&g[x],y,z);
      	add(&g[y],x,z);
      }

      while (_n>0)
      {
        	int x=h[1].nd;
        	s+=h[1].v;
        	use[x]=1;
        	_delete();

        	for (_aux=g[x]; _aux ; _aux=_aux->next)
        	{
               if (!use[_aux->x] && h[pos[_aux->x]].v >_aux->v)
               {
               	 pair[_aux->x]=x;
                 update(pos[_aux->x],_aux->v);
               }
        	}
      }

      printf("%lld\n%d\n",s,n-1);

      for (i=2;i<=n;++i)
      	 printf("%d %d\n",i,pair[i]);


	fclose(stdin);
	fclose(stdout);
	
	return 0;
}