#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 in,int sf)
{
	int i,j,temp,aux;
i=in; j=sf;
temp=G[(i+j)/2].cost;
	do
	{
		while(G[i].cost<temp) i++;
		while(G[j].cost>temp) j--;
	if(i<j)
	{
	aux=G[i].cost; G[i].cost=G[j].cost; G[j].cost=aux;
	aux=G[i].e1; G[i].e1=G[j].e1; G[j].e1=aux;
	aux=G[i].e2; G[i].e2=G[j].e2; G[j].e2=aux;
	}
		
	if(i<=j)
	i++,j--;
	
	}while(i<=j);
	
	if(in<j) sort(in,j);
	if(i<sf) sort(i,sf);
}

void afisare()
{
	for(i=1;i<=nrv;i++)
		costapm+=G[A[i]].cost;
	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;}
	
	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;}