#include<cstdio>
#include<iostream>

using namespace std;

const int Nmax = 200002;

int n,m,v_nr,V[Nmax];   // v_nr reprezinta numarul de elemente din vectorul v          
typedef struct muchie {int x,y,c,indice;}MUCHIE;
MUCHIE a[Nmax],v[Nmax];                                   // v reprezinta muchiile arborelui
FILE *in,*out;

int solve()
{
	int i,j,z,cost;                // z reprezinta indicele componentei conexe
	MUCHIE aux;
	for(i=1;i<m;i++)
		for(j=i+1;j<=m;j++)
			if(a[i].c>a[j].c)
			{
				aux=a[i];
				a[i]=a[j];
				a[j]=aux;
			}     for(i=1;i<=m;i++) cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].c<<endl;
	v_nr=1;               
	v[v_nr]=a[1];
	V[v[v_nr].x]=1;
	V[v[v_nr].y]=1;
	cost=v[v_nr].c;
	j=1;
	while( v_nr < n-1 )
	{
		j++;
		if(V[a[j].x]!=1 || V[a[j].y]!=1)
		{
			v_nr++;
			v[v_nr]=a[j];
			V[a[j].x]=1;
			V[a[j].indice]=1;
			cost=cost+v[v_nr].c;               
		}
	}
	return cost;
}

int main()
{
	int i;
	in=fopen("apm.in","r");
	out=fopen("apm.out","w");
	fscanf(in,"%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		fscanf(in,"%d %d %d",&a[i].x,&a[i].y,&a[i].c);
		a[i].indice=i;
		V[i]=i;
	}
	fprintf(out,"%d\n%d",solve(),v_nr);                 
	for(i=1;i<=v_nr;i++)
		fprintf(out,"\n%d %d",v[i].x,v[i].y); 
	fclose(in);
	fclose(out);
	return 0;
}