#include<cstdio>
#include<algorithm>
using namespace std;

struct gr{
	int x;
	int y;
	int c;
}a[200005];

int n,m,i,j,x,y,c,t,t1,t2,viz[100005],v1[100005],v2[100005];

int cmp(const gr a,const gr b)
{
	return a.c<b.c;
}

void citire()
{
	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",&x,&y,&c);
		a[i].x=x;
		a[i].y=y;
		a[i].c=c;
	}
	c=0;
}


void ver()
{
	t=x;
	while(t!=viz[t])t=viz[t];
	t1=t;
	t=y;
	while(t!=viz[t])t=viz[t];
	t2=t;
}

int main()
{
	citire();
	sort(a+1,a+m+1,cmp);
	for(i=1;i<=n;i++)viz[i]=i;
	for(j=1;j<=n-1;j++)
		for(i=1;i<=m;i++){
			x=a[i].x;
			y=a[i].y;
			ver();
			if(t1!=t2){
				c=c+a[i].c;
				v1[j]=x;
				v2[j]=y;
				viz[t2]=viz[t1];
				break;
			}
		}
	printf("%d\n",c);
	printf("%d\n",n-1);
	for(i=1;i<=n-1;i++)printf("%d %d\n",v1[i],v2[i]);
	return 0;
}