#include<stdio.h>
#include<algorithm>
using namespace std;
#define mmax 400002
#define nmax 200002
int n,m,s,nrs,t[nmax],nr[nmax],x[mmax],y[mmax],c[mmax],o[mmax],sol[mmax];

bool cmp(int x, int y)
{
	return c[x]<c[y];
}

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

void unite(int x, int y)
{
	if(nr[x]>nr[y])
		nr[x]+=nr[y],t[y]=x;
	else
		nr[y]+=nr[x],t[x]=y;
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i,j,k;
	for(i=1;i<=n;i++)
		t[i]=i,nr[i]=1;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x[i],&y[i],&c[i]);
		o[i]=i;
	}
	sort(o+1,o+m+1,cmp);
	for(i=1;i<=m;i++)
	{
		j=find(x[o[i]]);
		k=find(y[o[i]]);
		if(j!=k)
		{
			unite(j,k);
			s+=c[o[i]];
			sol[++nrs]=o[i];
		}
	}
	printf("%d\n%d\n",s,nrs);
	for(i=1;i<=nrs;i++)
		printf("%d %d\n",x[sol[i]],y[sol[i]]);
	return 0;
}