#include <cstdio>
#include <list>

using namespace std;

int inf=2000000000,sum=0;
int n,m,v[200006],d[200006],t[200006];
list<pair<int,int> > l[200006];
list<pair<int,int> >::iterator it;

void citire(){
	scanf("%d %d",&n,&m);
	int i,a,b,c;
	for(i=1;i<=m;i++){
		scanf("%d %d %d",&a,&b,&c);
		l[a].push_back(make_pair(b,c));
		l[b].push_back(make_pair(a,c));
	}
}	

void prim(){
	int i,min,poz=0;
	for(i=1;i<=n;i++){
		d[i]=inf;
		v[i]=0;
	}
	d[1]=0;
	t[1]=0;
	while(1){
		min=inf;
		for(i=1;i<=n;i++)
			if(v[i]==0 && d[i]<min){
				min=d[i];
				poz=i;
			}
		if(min==inf)
			break;
		sum+=min;
		v[poz]=1;
		for(it=l[poz].begin();it!=l[poz].end();++it)
			if(d[(*it).first]>(*it).second && v[(*it).first]==0){
				t[(*it).first]=poz;
				d[(*it).first]=(*it).second	;
			}	
	}
}

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

int main(){
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	citire();
	prim();
	afisare();
	return 0;
}