#include<cstdio>
using namespace std;
struct nod{int vf,cost;
		nod *next;};
nod *g[200004];
int n,m,t[200004],d[200004],v[200004];
void adaugare(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()
{
	int i,j,c;
	FILE *f=fopen("apm.in","r");
	fscanf(f,"%d %d",&n,&m);
	for(int i=0;i<=n;i++)
		g[i]=NULL;
		
	for(;m;m--)
		{
			fscanf(f,"%d %d %d",&i,&j,&c);
			adaugare(i,j,c);
			adaugare(j,i,c);
			
		}
	for(int i=0;i<=n;i++)
		v[i]=0,d[i]=1<<30,t[i]=-1;
	t[1]=0;
	v[1]=1;
	d[1]=0;
	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;
			s+=d[pmin];
			v[pmin]=1;
			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;
		}
	FILE *ff=fopen("apm.out","w");
	fprintf(ff,"%d\n%d\n",s,n-1);
	for(int i=1;i<=n;i++)
		if(t[i])
			fprintf(ff,"%d %d\n",i,t[i]);
	return 0;
}