#include <cstdio>
#include <cstdlib>
#include <algorithm>

typedef struct
{
	int x,y,c;
	bool bif;
} muchie;

muchie a[400000];
int gr[200000];

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

bool cmp(const muchie & a, const muchie & b)
{
	return a.c<b.c;
}

int main (int argc, char * const argv[]) {
	int n,m;
    fscanf(fin, "%d %d", &n, &m);
	for (int i=0; i<m; i++)
	{
		fscanf(fin, "%d %d %d",&a[i].x,&a[i].y,&a[i].c);
		a[i].x--;
		a[i].y--;
		a[i].bif=false;
	}
	for (int i=0; i<n; i++)
		gr[i]=i;
	std::sort(a,a+m,cmp);
	int i=0;
	int nrm=0;
	int sum=0;
	while (nrm<n-1)
	{
		if (gr[a[i].x]!=gr[a[i].y])
		{
			int grn=gr[a[i].x], gro=gr[a[i].y];
			for (int j=0; j<n; j++)
				if (gr[j]==gro)
					gr[j]=grn;
			a[i].bif=true;
			nrm++;
			sum+=a[i].c;
		}
		i++;
	}
	fprintf(fout, "%d\n%d\n",sum,n-1);
	for (int i=0; i<m; i++)
		if (a[i].bif)
			fprintf(fout, "%d %d\n", a[i].x+1, a[i].y+1);
	fclose(fin);
	fclose(fout);
    return 0;
}