using namespace std;
#define MAX 200000+5
#define INFINIT 2100000000
#include <cstdio>

struct nod{
	int capat;
	int cost;
	nod* next;
};

nod * a[MAX];
int n , d[MAX],t[MAX], v[MAX], H[MAX], vpoz[MAX], nH;

void read(){
	int m;
	nod *p;
	scanf("%d%d",&n,&m);
	nH = n;
	for( ; m ;--m){
		int i,j,c;
		scanf("%d%d%d",&i, &j, &c);
		p= new nod;
		p->next = a[i];
		p->capat = j;
		p->cost = c;
		a[i] = p;
		p = new nod;
		p -> capat =  i;
		p -> cost  = c;
		p -> next = a[j];
		a[j] = p;
	}
}

void afis(){
	for (int i=1;i<=n ; ++i){
		printf("%d :  ", i);
		nod *p = a[i];
		for( ; p ; p = p->next){
			printf("(%d %d) ",p->capat, p->cost);
		}
		printf("\n");
	}
}
int cost_minim=0;

void muta_sus(int nodul){
	//mut in sus in heap nodul nod
	int esteHeap = 0, i = nodul, aux;
	while(!esteHeap && i/2>0){
			if(d[H[i/2]]<d[H[i]])
				esteHeap = 1;
			else{
				aux = H[i]; H[i] = H[i/2]; H[i/2]=aux;
				vpoz[H[i]] = i;
				vpoz[H[i/2]] = i/2;
				i/=2;
			}
	}
}

void sterge(int nodul){
	H[nodul] = H[nH--];
	int esteHeap = 0, i = nodul, k, aux;
	while(!esteHeap && 2*i<=nH){
		k = 2*i;
		if(k+1<=nH && d[H[k]] >d[H[k+1]])
			k++;
		if(d[H[i]]<d[H[k]])
			esteHeap = 1;
		else{
			aux = H[i]; H[i] = H[k]; H[k] = aux;
			vpoz[H[i]] = i;
			vpoz[H[k]] = k;
			i=k;
		}
	}
}

void scriee(){
	for(int i =1;i<=n;i++)
		printf("%3d",i);
	printf("\n");
	for(int i =1;i<=n;i++)
		if(d[i]<INFINIT)
			printf("%3d",d[i]);
		else
			printf("  -");
	printf("\n");
	for(int i =1;i<=nH;i++)
		printf("%3d",H[i]);
	printf("\n");
}

void prim(int start){
	for(int i = 0; i<= n; i++){
		d[i]=INFINIT, v[i] = 0, t[i] = -1;
		
			H[i] = i, vpoz[i] = i;
	}
	sterge(start);
	v[start] = 1; d[start]=0;	t[start]= 0;
	for(nod *p = a[start]; p ; p = p->next){
		d[p->capat] =p->cost, t[p->capat] = start;
		muta_sus(vpoz[p->capat]);
	}
	//scriee();
	for(int ll=n-1; ll ; --ll){
		int  poz = H[1];
		sterge(1);
		v[poz]=1;
		//printf("poz= %d\n", poz);
		cost_minim+=d[poz];
		for(nod * p = a[poz] ; p ; p = p->next)
			if(v[p->capat] == 0 && d[p->capat] >  p->cost){
				d[p->capat] = p->cost, t[p->capat] = poz ;
				muta_sus(vpoz[p->capat]);
		}
		//scriee();
	}
}

void write(){
	printf("%d\n%d\n",cost_minim, n-1);
	for(int i=1;i<=n;++i)
		if(t[i])
			printf ("%d %d\n",i,t[i]);
}

int main(){
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	read();
//	afis();
	prim(1);
	write();
}