#include<stdio.h>
#include<stdlib.h>
#define NMAX 200000
#define MMAX 400000

int n,m,cc[NMAX+1],costtotal;

struct muchie{
	int x,y,c;
};
typedef muchie *pm;
muchie v[MMAX],h[NMAX+1];

int fcmp(void const *a,void const *b){
	return ((pm)a)->c-((pm)b)->c;
}

void apm(){
	int i=0,j=0,ms=0,min,max,k=0;
	while(ms<n-1){
		while(cc[v[i].x]==cc[v[i].y]) i++;
		h[k]=v[i],k++;
		costtotal+=v[i].c;
		if(v[i].x<v[i].y){
			min=cc[v[i].x];
			max=cc[v[i].y];
		}
		else{
			min=cc[v[i].y];
			max=cc[v[i].x];
		}
		for(j=1;j<=n;j++)
			if(cc[j]==max)
				cc[j]=min;
		ms++;

	}
}

int main(){
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
int i;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
	scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
qsort(v,m,sizeof(v[0]),fcmp);
for(i=1;i<=n;i++)
	cc[i]=i;
apm();
printf("%d\n%d\n",costtotal,n-1);
for(i=0;i<n-1;i++)
	printf("%d %d\n",h[i].x,h[i].y);
return 0;
}