#include<stdio.h>
#include<algorithm>
#define  maxn 400100

using namespace std;

int gr[maxn],x[maxn],y[maxn],c[maxn];
int N,m,ANS,ind[maxn];
int poz[maxn];

int grupa(int i)
{
	if (gr[i]==i)
          return i;
	gr[i]=grupa(gr[i]);
	return gr[i];
}

void reuniune(int i,int j)
{
	gr[grupa(i)]=grupa(j);
}

bool cmpf(int i,int j)
{
	return(c[i]<c[j]);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d\n",&N,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d %d %d\n",&x[i],&y[i],&c[i]);
		ind[i]=i;
	}

	for(int i=1;i<=N;i++)
          gr[i]=i;
	sort(ind+1,ind+m+1,cmpf);
     int num=0;
	for(int i=1;i<=m;i++)
	{
		if (grupa(x[ind[i]])!=grupa(y[ind[i]]))
		{
			ANS+=c[ind[i]];
			reuniune(x[ind[i]],y[ind[i]]);
			poz[num++]=ind[i];
		}
	}
	printf("%d\n",ANS);
	printf("%d\n",N-1);
	for(int i=0;i<N-1;i++)
		printf("%d %d\n",x[poz[i]],y[poz[i]]);
	return 0;
}