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

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

struct muchie{
	int x,y,c;
};
typedef muchie *pm;
muchie v[MMAX],h[NMAX+1];
struct set{
	int parent;
	};
set vs[NMAX+1];
void Makeset(int x){
cc[x]=x;
}
int Find(int x){
if(cc[x]==x) return x;
else return Find(cc[x]);
}
void Union(int x,int y){
int xroot=Find(x),yroot=Find(y);
cc[y]=cc[x];
}
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;
	int pmin,pmax;
	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++;
	}
}

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;
}