#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "apm.in"
#define file_out "apm.out"

int i,j,c[210000],x[210000],y[210000],n,m,t1,t2,tata[210000],ind[210000],sol;

int cmp(int a, int b)
{
	return c[a]<c[b];
}


int find(int x)
{
	if (tata[x]!=x) tata[x]=find(tata[x]);
	return tata[x];
}


void uneste(int i, int j)
{
	tata[i]=j;
}


int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	for (i=1;i<=n;++i) tata[i]=i;
	
	for (i=1;i<=m;++i)
	{
		scanf("%d %d %d", &x[i], &y[i], &c[i]);
		ind[i]=i;
	}
	sol=0;
	
	sort(ind+1,ind+m+1,cmp);
	int nr=0;
	int q[201020];
	for (i=1;i<=m;++i)
	{
		t1=find(x[ind[i]]);
		t2=find(y[ind[i]]);
		
		if (t1!=t2)
		{
			uneste(t1,t2);
			sol+=c[ind[i]];
			q[++nr]=ind[i];
		}
	}

	printf("%d\n", sol);
	printf("%d\n", n-1);
	for (i=1;i<=nr;++i)
		 printf("%d %d\n", x[q[i]],y[q[i]]);
	
	return 0;
}