#include <fstream.h>
#define dim 20000
#define inf 2000
ifstream fin("apm.in");
ofstream fout("apm.out");


int n,m,nod,nr;
int a[dim][dim];
int t[dim],min,max,h[dim],poz[dim];
long cost;


void swap(int i, int j)
{int aux;
aux=h[i]; h[i]=h[j]; h[j]=aux;
poz[h[i]]=i; poz[h[j]]=j;
}

void heap_down(int k)
{int fiu;
do{fiu=0;
   if (2*k<=n)
    {fiu=2*k;
     if (fiu+1<=n && a[h[fiu]][t[h[fiu]]]>a[h[fiu+1]][t[h[fiu+1]]]) 
		 fiu++;
	}
	
	if (a[h[k]][t[h[k]]]<a[h[fiu]][t[h[fiu]]]) fiu=0;
	
	if (fiu>0)
	{swap(fiu,k);
	 k=fiu;
	}
}while (fiu>0);
}

void heap_up(int k)
{while (k>1 && a[h[k/2]][t[h[k/2]]]>a[h[k]][t[h[k]]])
   {swap(k,k/2);
    k=k/2;
   }
}   


void extrage(int k)
{h[k]=h[n];
n--;
 if (k>1 && a[h[k/2]][t[h[k/2]]]>a[h[k]][t[h[k]]])
	 heap_up(k);
 else heap_down(k);
}



int main()
{int i,j,x,y,c;

fin>>n>>m;
for (i=1;i<=n;i++) 
	for (j=i+1;j<=n;j++)
		a[i][j]=a[j][i]=inf;
	
for (i=1;i<=m;i++) {fin>>x>>y>>c; if (a[x][y]>c) a[x][y]=a[y][x]=c;}


for (i=2;i<=n;i++)
 t[i]=1;


 m=n;

for (n=0,i=2;i<=m;i++)
 {n++;
  h[n]=i; poz[i]=n;
  heap_up(n);
 }
 
 
while (n)
  {nod=h[1];
   extrage(1);
   
   cost+=a[nod][t[nod]];
   t[nod]=-t[nod];
   
   for (i=1;i<=m;i++)
	   if (t[i]>0 && a[i][t[i]]>a[i][nod])
		   {t[i]=nod;
	        heap_up(poz[i]);
		   }
	   
	}

fout<<cost<<'\n'<<m-1<<'\n';  
for (i=2;i<=m;i++)
fout<<i<<" "<<-t[i]<<'\n';	
fout.close();
return 0;
}