#include<stdio.h>
#include<stdlib.h>
#define N 200001
#define inf 1<<30

FILE *f=fopen("APM.in","r");
FILE *g=fopen("APM.out","w");

int n,m,L,cate,nr;
int C[N],P[N],H[N],Poz[N],viz[N];

struct nod{

	int nd;
	int ct;

	nod* nx;

};

nod* G[N];

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

void ADD(nod*& p,int catre,int cost){

	nod *q = new nod;
	q->nx = p;
	q->nd = catre;
	q->ct = cost;
	p = q;
}

void AFISARE(){
	int i,total=0;
	for(i=1;i<=n;i++) total+=C[i];
	fprintf(g,"%d\n%d\n",total,--cate);
	for(i=2;i<=n;i++)fprintf(g,"%d %d\n",Poz[i],i);
}

void DOWN(int x){
	int f;
	while(f<=L){
		f = x<<1;
		if(f<=L){
		  if(f+1<=L)
		    if(C[H[f]] > C[H[f+1]]) f++;
		}else return;
		if(C[H[x]] > C[H[f]]){
			swap(H[x],H[f]);
			swap(P[H[x]],P[H[f]]);
			x=f;
		}else return;
	}


}

void UP(int x){
	int t;
	while(x>1){
		t = x>>1;

		if(C[H[t]] > C[H[x]]){
			swap(H[t],H[x]);
			swap(P[H[t]],P[H[x]]);
			x=t;
		}
		else return;
	}
}

inline void INSERT(int x){

	H[++L]=x;
	P[H[L]]=L;
	cate++;
	UP(L);
}

inline void REMOVE(){

	swap(H[1],H[L--]);
	P[H[1]]=1;
	DOWN(1);

}

void date(){

	fscanf(f,"%d %d",&n,&m);
	int x,y,c,i;
	for(; m-- ;){
		fscanf(f,"%d%d%d",&x,&y,&c);
		ADD(G[x],y,c);
		ADD(G[y],x,c);
	}
	for(i=1;i<=n;i++) { C[i]=inf;P[i]=-1; }

	INSERT(1);C[1]=0;nr = n-1;

}

void APM(){
	int min;

	for(; nr ;){

		min = H[1];
		viz[min]=1;
		REMOVE();
		nod *q=new nod;
		q = G[min];
		nr--;
		for(;q;q=q->nx){
			if(!viz[q->nd] && C[q->nd] >= q->ct){
				C[q->nd] = q->ct;
				Poz[q->nd] = min;
				if(P[q->nd]!=-1) UP(P[q->nd]);
				else INSERT(q->nd);
			}
		}
	}
}

int main(){

	date();
	APM();
	AFISARE();
	return 0;
}