#include <stdio.h>
#include <algorithm>
#define MM 400001
#define NM 200001
struct muchie{int x,y,c;} e[MM],sol[NM];
int nrsol;
long long sum;
int r[NM];
int n,m;
using namespace std;
inline int cmp(muchie a,muchie b)
{if (a.c<b.c) return 1;
 return 0;
}
int rad(int x)
{if (r[x]==x) return x;
 r[x]=rad(r[x]);
 return r[x];
}
int main()
{freopen("apm.in","r",stdin);
 freopen("apm.out","w",stdout);
 scanf("%d %d",&n,&m);
 int i;
 for (i=1;i<=m;i++)
	 scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].c);
 sort(e+1,e+m+1,cmp);
 for (i=1;i<=n;i++) r[i]=i;
 for (i=1;i<=m&&nrsol!=n-1;i++)
	 {if (rad(e[i].x)!=rad(e[i].y))
		 {sum+=e[i].c;
		  nrsol++;
		  sol[nrsol]=e[i];
		  r[r[e[i].x]]=r[e[i].y];
		 }
	 }
 printf("%lld\n",sum);
 printf("%d\n",n-1);
 for (i=1;i<=nrsol;i++)
	 printf("%d %d\n",sol[i].x,sol[i].y);
 return 0;
}