#include<cstdio>
#include<algorithm>
using namespace std;
struct gr{
	int x;
	int y;
	int c;
}a[400001];
int n,m,i,j,k,s,viz[200001],sol[200001];


bool cmp(const gr a1,const gr a2)
{
	return a1.c<a2.c;
}

void re(int t)
{
	while (t!=viz[t])t=viz[t];
	for(j=1;j<=n;j++)
		if(viz[j]==t)viz[j]=viz[a[i].y];
}

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",&a[i].x,&a[i].y,&a[i].c);
		viz[a[i].x]=a[i].x;
		viz[a[i].y]=a[i].y;
	}
}

int main()
{
	citire();
	sort(a+1,a+m+1,cmp);
	i=0;
	while (k<n-1){
		i++;
		if(viz[a[i].x]!=viz[a[i].y]){
			k++;
			s=s+a[i].c;
			sol[k]=i;
			re(a[i].x);
		}
	}
	printf("%d\n%d\n",s,k);
	for(i=1;i<=k;i++)printf("%d %d\n",a[sol[i]].x,a[sol[i]].y);
	return 0;
}