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

void read(){
	int m;
	nod *p;
	scanf("%d%d",&n,&m);
	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 prim(int start){
	for(int i = 0; i<= n; i++)
		d[i]=INFINIT, v[i] = 0, t[i] = -1;
	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;
	for(int ll=n-1; ll ; --ll){
		int  poz = 0;
		for(int i = 1; i<=n ;i ++)
			if(v[i]==0 && d[i]<=d[poz])
				poz=i;
		v[poz]=1;
		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 ;
	}
}

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