using namespace std;
#include <cstdio>

struct nod{
	int vf,cost;
	nod * next;
};

nod * G[200002];
int n,t[200002],v[200002],d[200002];

void addMuchie(int i,int j,int c){
	//adauga pe j in lista de vecini ai lui i
	nod *p=new nod;
	p->vf=j , p->cost=c;
	p->next = G[i];
	G[i]=p;
}

int main(){
	freopen("apm.in","r",stdin);
	int m,i,j,c;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		G[i]=NULL;
	for( ; m ; --m){
		scanf("%d%d%d",&i,&j,&c);
		addMuchie(i,j,c);
		addMuchie(j,i,c);
	}
	for(i=1;i<=n;++i)
		t[i]=-1, v[i]=0,d[i]=1<<30;
	t[1]=0;
	v[1]=1;
	d[1]=0;
	d[0]=1<<30;
	for(nod *p=G[1] ; p ; p=p->next)
		d[p->vf]=p->cost , t[p->vf] = 1;
	int s=0;
	for(int k=1;k<n;++k){
		int pmin=0;
		for(i=1;i<=n;++i)
			if(d[i]<d[pmin] && v[i]==0)
				pmin=i;
		v[pmin]=1;
		s += d[pmin];
		for(nod *p=G[pmin]; p ; p=p->next)
			if(d[p->vf] > p->cost && v[p->vf]==0)
				d[p->vf] = p->cost, t[p->vf] = pmin;
		
	}
	freopen("apm.out","w",stdout);
	printf("%d\n%d\n",s,n-1);
	for(i=1;i<=n;++i)
		if(t[i]!=0)
			printf("%d %d\n",i,t[i]);
	return 0;
}