# include <stdio.h>
# include <algorithm>
using namespace std;
struct nod {int x,y,c;} a[400010];
struct nod1{int x,y;} c[400010];
int n,m,i,b[400010],k,suma,q,nr;
bool cmp (const nod &p,const nod &p1)
{
	return (p.c<p1.c);
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	for (i=1; i<=m; i++)
		scanf("%d %d %d\n",&a[i].x,&a[i].y,&a[i].c);
	sort(a+1,a+m+1,cmp);
	for (i=1; i<=n; i++)
		b[i]=i;
	suma=0; nr=0;
	for (i=1; i<=m; i++)
	{
		if (b[a[i].x]!=b[a[i].y])
		{
			suma+=a[i].c;
			q=b[a[i].x];
			nr++;
			c[nr].x=a[i].x;
			c[nr].y=a[i].y;
			for (k=1; k<=n; k++)
				if (b[k]==q) b[k]=b[a[i].y];
		}
	}
	printf("%d\n",suma);
	printf("%d\n",nr);
	for (i=1; i<=nr; i++)
		printf("%d %d\n",c[i].x,c[i].y);
	return 0;
}