#include<stdio.h>
#define IN "APM.in"
#define OUT "APM.out"
#define INF 1<<30
#define MAX 200001

FILE *f=fopen(IN,"rt");
FILE *g=fopen(OUT,"wt");

struct NOD {
	int nod,cost;
	NOD* next;
};
NOD* G[MAX];
int ct[MAX],p[MAX],poz[MAX],h[MAX],viz[MAX];
int n,m,nr,start=1,lh,total,cate;

inline void swap(int& a,int& b){
	int aux=a;
	a=b;b=aux;
}



inline void add(NOD*& p, int nd,int c){

	NOD* q=new NOD;
	q->next=p;
	q->nod=nd;
	q->cost=c;
	p=q;
}

void down_heap(int x){
	int f;
	while(x<=lh){
		f=x<<1;
		if(f<=lh){
			if(f+1<=lh)
				if(ct[h[f]]>ct[h[f+1]]) f++;
		}else return;
		if(ct[h[x]]>ct[h[f]]){
			poz[h[x]]=f;
			poz[h[f]]=x;
			swap(h[x],h[f]);
			x=f;
		}else return;
	}
}

void up_heap(int x){
	int t;
	while(x>1){
		t = x>>1;
		if(ct[h[t]]>ct[h[x]]){
			poz[h[x]]=t;
			poz[h[t]]=x;
			swap(h[t],h[x]);
			x=t;
		}else return;
	}
}

void afisare(){
	int i;total=0;
	for(i=2;i<=n;i++)total+=ct[i];
	fprintf(g,"%d\n%d\n",total,--cate);
	for(i=2;i<=n;i++)fprintf(g,"%d %d\n",p[i],i);



}

inline insert(int x){
 h[++lh]=x;
 poz[h[lh]]=lh;
 cate++;
 up_heap(lh);
}

inline remove(){
	swap(h[1],h[lh--]);
	poz[h[1]]=1;
	down_heap(1);
}

void date(){
	int x,y,c,i;
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++){
	 fscanf(f,"%d%d%d",&x,&y,&c); add(G[x],y,c);add(G[y],x,c);
	}
	for(i=1;i<=n;i++){ct[i]=INF;poz[i]=-1;}
	insert(1);ct[1]=0;nr=n-1;


}

void APM(){
for(;nr;){
int min;
min=h[1];
viz[min]=1;
remove();
NOD*q=new NOD;
q=G[min];
nr--;
for(;q;q=q->next){
	if(!viz[q->nod] && ct[q->nod]>=q->cost){
		ct[q->nod]=q->cost;
		p[q->nod]=min;
	       if(poz[q->nod]!=-1)up_heap(poz[q->nod]);
	       else insert(q->nod);

	}
}

}
}


int main(){
	date();
	APM();
	afisare();
return 0;
}