#include<stdio.h>
#include<stdlib.h>
#define nmax 200003
#define mmax 400009

int n,m,i,j;
long long sum=0;
int komp[nmax];
int ered[mmax], seged;
struct asd{int a; int b; int c;};
asd el[mmax];

int cmp(const void *a, const void *b)
{return ((asd *)a)->c-((asd *)b)->c;}


int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for(i=1;i<=m;i++)
		scanf("%d %d %d", &el[i].a, &el[i].b, &el[i].c);
	el[0].c=-nmax;
	for(i=1;i<=n;i++)
		komp[i]=i;
	qsort(el, m+1, sizeof(asd), cmp);
	for(i=1;i<=m;i++)
			if(komp[el[i].a]!=komp[el[i].b])
			{
				seged=komp[el[i].b];
				for(j=1;j<=n;j++)
					if(komp[j]==seged)
						komp[j]=komp[el[i].a];
				sum+=el[i].c;
				ered[++ered[0]]=i;
			}
	printf("%lld\n%d\n", sum, ered[0]);
	for(i=1;i<=ered[0];i++)
		printf("%d %d\n", el[ered[i]].a, el[ered[i]].b);
	return 0;
}