#include <cstdio>
#include <list>

using namespace std;

int inf=2000000000,sum=0;
int n,m,d[200006],t[200006],h[200006],k,pozitie[200006],inh[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 downheap(){
	h[1]=h[k];
	k--;
	int tata=1,fiu1=2,fiu2=3,min,aux;
	while(fiu1<=k){
		if(fiu2>k)
			min=fiu1;
		else if(d[h[fiu1]]>d[h[fiu2]])
			min=fiu2;
		else min=fiu1;
		if(d[h[tata]]>d[h[min]]){
			pozitie[h[tata]]=min;
			pozitie[h[min]]=tata;
			aux=h[tata];
			h[tata]=h[min];
			h[min]=aux;
		}			
		else return;
		tata=min;
		fiu1=tata*2;
		fiu2=fiu1+1;
	}
}	

void upheap(int poz){
	int fiu=poz;
	int nod=h[poz];
	int tata=fiu/2;
	while(tata!=0 && d[h[tata]]>d[nod]){
		pozitie[h[tata]]=fiu;
		h[fiu]=h[tata];
		fiu=tata;
		tata=fiu/2;
	}
	pozitie[nod]=fiu;
	h[fiu]=nod;
}		
			

void prim(){
	int i,poz=0;
	for(i=1;i<=n;i++){
		d[i]=inf;
	}
	d[1]=0;
	t[1]=0;
	h[1]=1;
	inh[1]=1;
	k=1;
	while(k!=0){
		poz=h[1];
		sum+=d[poz];
		downheap();
		inh[poz]=0;
		d[poz]=-inf;
		for(it=l[poz].begin();it!=l[poz].end();++it)
			if(d[(*it).first]>(*it).second){
				d[(*it).first]=(*it).second;
				t[(*it).first]=poz;
				if(inh[(*it).first]==1){
					upheap(pozitie[(*it).first]);
				}
				else {
					k++;
					inh[(*it).first]=1;
					h[k]=(*it).first;
					//pozitie[(*it).first]=k;
					upheap(k);
				}
			}	
	}
}

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