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

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

muchie a[400000];
bool bif[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;
	}
	memset(bif, 0, sizeof(bool)*n);
	bif[0]=true;
	std::sort(a,a+m,cmp);
	int sum=0;
	for (int i=0; i<n-1; i++)
		for (int j=0; j<m; j++)
		{
			if (a[j].bif) continue;
			if (bif[a[j].x]^bif[a[j].y])
			{
				bif[a[j].x]=bif[a[j].y]=true;
				a[j].bif=true;
				sum+=a[j].c;
				break;
			}
		}
	
	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;
}