#include<stdio.h>
#include<stdlib.h>
#define NMAX 200001
#define MMAX 400001

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

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

void Makeset(int x){
cc[x]=x;hi[x]=1;
}

int Find(int x){
int r=x;
while(cc[r]!=r) r=cc[r];
int i=x,j;
while(i!=r){
	j=cc[i],cc[i]=r,i=j;
	}
return r;
}
void Union(int x,int y){
int xroot=Find(x),yroot=Find(y);
if(hi[xroot]>hi[yroot]) cc[yroot]=xroot;
else if(hi[yroot]>hi[xroot]) cc[xroot]=yroot;
	 else cc[yroot]=xroot,hi[xroot]++;
}
int fcmp(void const *a,void const *b){
	return ((pm)a)->c-((pm)b)->c;
}

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

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++) {Makeset(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;
}