#include<stdio.h>
using namespace std;
#define nrVF 200005
#define nrMuchii 400005

int n,m,A[nrVF],c[nrVF],i,j,nrv,costapm,min,max;

struct Muchie {int e1,e2,cost; }; 

Muchie G[nrMuchii];

FILE *f=fopen("apm.in","r"), *g=fopen("apm.out","w");

void initializare()
{
	fscanf(f,"%d %d",&n,&m);
for(i=1;i<=m;i++)
	fscanf(f,"%d %d %d",&G[i].e1,&G[i].e2,&G[i].cost);

for(i=1;i<=n;i++)
	c[i]=i;
fclose(f);
}
void sort(int prim, int ultim)
{int i,j;
Muchie x;

if(prim<ultim)
 {x=G[prim]; i=prim; j=ultim;
   while(i<j)
   {while(i<j && G[j].cost>=x.cost) j--;
     G[i]=G[j];
    while(i<j && G[i].cost<=x.cost) i++;
	  G[j]=G[i];
   }
   G[i]=x;
   
sort(prim, i-1);
sort(i+1,ultim);
 }
}

void afisare()
{
	
	fprintf(g,"%d \n%d\n", costapm,n-1);
	
	for(i=1;i<=nrv;i++)
		fprintf(g,"%d %d\n",G[A[i]].e1,G[A[i]].e2,G[A[i]].cost);
	
fclose(g);
}

int main()
{
	
initializare();
sort(1,m);

for(i=1; nrv<n-1; i++)
{
	if(c[G[i].e1]!=c[G[i].e2])
		{nrv++;	A[nrv]=i; costapm+=G[i].cost;}
	
	if(c[G[i].e1]<c[G[i].e2])
		{
		min=c[G[i].e1];
		max=c[G[i].e2];
		}
	else 
		{
		min=c[G[i].e2];
		max=c[G[i].e1];
		}
	for(j=1;j<=n;j++)
		if(c[j]==max)
			c[j]=min;
			
}

afisare();	
	
	
return 0;}