#include<cstdio>
using namespace std;
struct nod{int vf,cost;
		nod *next;};
nod *g[200000];
int n,m,t[200000],d[200000],v[200000];
int radacina (int x)
{
	int tmp,y;
	while(t[x])x=t[x];
	y=x;
	while(t[y])tmp=t[y],t[y]=x,y=tmp;
	return x;
}
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=1;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;
	t[1]=-1;
	t[0]=0;
	v[0]=1;
	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]&&d[i]==0)pmin=i;
			s+=d[pmin];
			v[pmin]=1;
			for(nod*p=g[pmin];p;p=p->next)
				if(d[p->vf]&&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++)
		fprintf(ff,"%d %d",i,t[i]);
	return 0;
}