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

	 struct muchie{int a,b,c;}v[4004];

	 int sol[4002];
	 int i,p,k,cost=0,m,n,nr[2002],tt[2040];

	int cmp(muchie a,muchie b){

	return a.c<b.c;}


	void merge(int a,int b){
	if(nr[a]>nr[b])
		tt[b]=a;
	else
		tt[a]=b;
	}

	int find(int val){
	int r=val,y;
	for(;tt[r]!=r;r=tt[r]);

	for(;tt[val]!=val;){
		y=tt[val];
		tt[val]=r;
		val=y;
		}

	return r;
	}

	int main(){

	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d",&n,&m);

	for(i=1;i<=n;i++)
			  {tt[i]=i;
				nr[i]=1;
			  }

	for(i=1;i<=m;i++)
			  scanf("%d %d %d",&v[i].a,&v[i].b,&v[i].c);

	sort(v+1,v+1+m,cmp);

	for(i=1;i<=m;i++)
			  if(find(v[i].a)!=find(v[i].b))
						 {cost+=v[i].c;
						 k++;
						 sol[k]=i;
						 merge(find(v[i].a),find(v[i].b));}

	printf("%d\n%d\n",cost,k);

	for(i=1;i<=k;i++)
			  printf("%d %d\n",v[sol[i]].a,v[sol[i]].b);

	return  0;}