#include<stdio.h>
#include<algorithm>
using namespace std;
int m,n,i,j,t[200009],h[200009],nr,cost,sol[2][200009],q;
bool ok[200009];
struct muchie
{
	int a,b,c;
}v[400009];
inline bool cmp(muchie a, muchie b)
{
	return(a.c<b.c);
}
inline bool check(int a, int b)
{
	while(a!=t[a])a=t[a];
	while(b!=t[b])b=t[b];
	return(a==b);
}
inline void uneste(int a, int b)
{
	while(a!=t[a])a=t[a];
	while(b!=t[b])b=t[b];
	if(h[a]>h[b]){t[b]=a;return;}
	if(h[a]<h[b]){t[a]=b;return;}
	t[b]=a;
	++h[a];
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)t[i]=i,h[i]=1,ok[i]=0;
	for(i=0;i<m;++i)scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].c);
	sort(v,v+m,cmp);
	nr=i=cost=q=0;
	while(nr<n-1)
	{
		if(!check(v[i].a,v[i].b))
		{
			uneste(v[i].a,v[i].b);
			cost+=v[i].c;
			++nr;
			sol[0][q]=v[i].a;
			sol[1][q]=v[i].b;
			++q;
		}
		++i;
	}
	printf("%d\n%d\n",cost,n-1);
	for(i=0;i<q;++i)
		printf("%d %d\n",sol[0][i],sol[1][i]);
	return 0;
}