#include<stdio.h>
#include<algorithm>
#define MAX 200001
using namespace std;
int car[MAX],n,m;
struct muchie
{
	int x,y,c,a;
}v[MAX];
int cmp(muchie a, muchie b)
{
	return (a.c<b.c);
}
int main()
{
	FILE*f = fopen("apm.in","r");
	fscanf(f,"%d%d",&n,&m);
	int i;
	for(i=1;i<=m;++i)
		fscanf(f,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
	fclose(f);
	
	sort(v+1, v+1+m, cmp);
	car[v[1].x] = car[v[1].y] = 1;
	v[1].a = 1;
	int cont,max,p,cost = v[1].c;
	cont = 1;
	while(cont<n-1)
	{
		for(i=2;i<=m;++i)
		if((!car[v[i].x] || !car[v[i].y]) && (car[v[i].x] || car[v[i].y]))
		{
			p=i;
			i=m;
		}
		car[v[p].x] = car[v[p].y] = 1;
		v[p].a = 1;
		cost += v[p].c;
		++cont;
	}
	FILE*g=fopen("apm.out","w");
	fprintf(g,"%d\n%d\n",cost,n-1);
	for(i=1;i<=m;++i)
		if(v[i].a)fprintf(g,"%d %d\n",v[i].x, v[i].y);
	fclose(g);
	return 0;
}