#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];

struct nod{
	int info;
	nod *adr;
};
typedef nod *pnod;

struct lista{
	int nr;
	pnod vf,sf;
};

lista l[NMAX+1];

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,st,dr;
	pnod nc;
	while(ms<n-1){
		while(cc[v[i].x]==cc[v[i].y]) i++;
		h[k]=v[i],k++;
		costtotal+=v[i].c;
		if(l[cc[v[i].x]].nr<l[cc[v[i].y]].nr){
			min=l[cc[v[i].x]].nr;
			max=l[cc[v[i].y]].nr;
			st=cc[v[i].x],dr=cc[v[i].y];
		}
		else{
			min=l[cc[v[i].y]].nr;
			max=l[cc[v[i].x]].nr;
			st=cc[v[i].y],dr=cc[v[i].x];

		}
		nc=l[st].vf;
		while(nc){
			cc[nc->info]=dr;
			nc=nc->adr;
		}
		l[dr].nr+=min;
		l[st].nr=0;
		l[dr].sf->adr=l[st].vf;
		l[dr].sf=l[st].sf;
		l[st].vf=NULL;
		ms++;

	}
}

int main(){
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
int i;
pnod nn;
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;
	nn=new nod;
	nn->info=i;
	nn->adr=NULL;
	l[i].vf=nn;
	l[i].sf=nn;
	l[i].nr=1;
}
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;
}