#include <stdio.h>
#include <algorithm>

FILE *fin=fopen("apm.in","r");
FILE *fout=fopen("apm.out","w");

class muchie
{
public:
	int x,y,c;
	bool used;
	muchie():used(false)
	{
	}
	bool operator<(const muchie& othr) const
	{
		return this->c<othr.c;
	}
};

muchie a[1024];
int g[1024];


int main (int argc, char * const argv[]) {
	int n,m;
    fscanf(fin, "%d %d",&n,&m);
	for (int i=1; i<=n; i++)
		g[i]=i;
	for (int i=0; i<m; i++)
	{
		fscanf(fin, "%d %d %d",&a[i].x,&a[i].y,&a[i].c);
	}
	std::sort(a,a+m);
	int k=0;
	long long sum=0;
	for (int i=0; i<m; i++)
	{
		if (g[a[i].x]!=g[a[i].y])
		{
			int x=g[a[i].y];
			for (int j=1; j<=n; j++)
				if (g[j]==x)
					g[j]=g[a[i].x];
			a[i].used=true;
			sum+=a[i].c;
			k++;
			if (k>=n-1)
				break;
			
		}
	}
	fprintf(fout, "%d\n%d\n",sum,k);
	for (int i=0; i<m; i++)
		if (a[i].used)
			fprintf(fout, "%d %d\n",a[i].x,a[i].y);
	fclose(fin);
	fclose(fout);
    return 0;
}