#include<stdio.h>
#include<algorithm>
using namespace std;
int m,n,i,j,k,S,q,s[200010];
struct sir
{
	int st;
	int dr;
	int cst;
};
sir v[400010],sir2[400010];
int cmp(sir a, sir b)
{
	return a.cst<b.cst;
}
int find(int x)
{
	int r;
	r=x;
	while(s[r]!=r)r=s[r];
	while(s[x]!=x){x=s[x];s[x]=r;}
	return r;
}
int main()
{
	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",&v[i].st,&v[i].dr,&v[i].cst);
	sort(v+1,v+m+1,cmp);
	for(i=1;i<=n;i++)
		s[i]=i;
	for(i=1;i<=m;i++)
	{
		j=find(v[i].st);
		k=find(v[i].dr);
		if(j!=k)
		{
			S+=v[i].cst;
			sir2[q]=v[i];
			q++;
			s[k]=j;
		}
	}
	printf("%d\n",S);
	printf("%d\n",q);
	for(i=0;i<q;i++)
		printf("%d %d\n",sir2[i].st,sir2[i].dr);
	return 0;
}