#include<stdio.h>
#include<algorithm>
using namespace std;

struct jag
{int x,y,c,f;};
jag a[400010];
int t[400010],h[400010];

int cmp(jag n,jag m)
{return n.c<m.c;}
////////////////////
int find(int n)
{
for(;t[n]!=n;n=t[n]);
return n;
}

void unite(int n,int m)
{
if(h[n]>h[m])
	t[m]=n;
else
if(h[m]==h[n])
	{
	h[n]++;
	t[m]=n;
	}
else
	t[n]=m;
}
////////////////////
int main()
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
int n,m,i;
long s=0;
scanf("%d%d",&n,&m);

for(i=1;i<=n;i++)
	t[i]=i;
for(i=1;i<=m;i++)
	scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
sort(a+1,a+m+1,cmp);

int rx,ry,aux=n-1;
i=0;
while(n>1)
{
i++;
rx=find(a[i].x);
ry=find(a[i].y);
if(rx!=ry)
	{
	n--;	
	s=s+a[i].c;
	a[i].f=1;
	unite(rx,ry);
	}	
}

printf("%ld\n%d\n",s,aux);
for(i=1;i<=m;i++)
	if(a[i].f==1)
		printf("%d %d\n",a[i].x,a[i].y);
return 0;
}