#include<cstdio>
#define Nmax 200001
using namespace std;

struct NodAR
{
	int inf,cst;
	struct NodAR* next;
};

typedef NodAR* NAR;

NAR a[Nmax];

int N,M,viz[Nmax],v[Nmax],pc[Nmax],ok1;

void read();
void solve();
void write();
void adaug(int x,int y,int c);

int main()
{
	freopen ("apm.in","r",stdin);
	freopen ("apm.out","w",stdout);
	read();
	solve();
	write();
	return 0;
}

void read()
{
	int i,x,y,c;
	scanf("%ld%ld",&N,&M);
	for (i=1;i<=M;++i)
	{
		scanf("%ld%ld%ld",&x,&y,&c);
		adaug(x,y,c);
		adaug(y,x,c);
	}
}

void adaug (int x,int y,int c)
{
	NAR p=new NodAR;
	p->inf=y;
	p->cst=c;
	p->next=a[x];
	a[x]=p;
}

void solve()
{
	int i,x,y,min,pos,j;
	NAR p;
	viz[1]=1;
	for (i=2;i<=N;v[i]=1001,pc[i]=1,++i);
	for (p=a[1];p;p=p->next)
	{
		y=p->inf;
		x=p->cst;
		v[y]=x;
	}
	i=N-1;
	while (i)
	{
		min=1001; pos=0;
		for (j=2;j<=N;++j)
			if (viz[j]==0&&v[j]<min)
			{ min=v[j]; pos=j; }
		for (p=a[pos];p;p=p->next)
			{
				y=p->inf;
				x=p->cst;
				if (viz[y]==0&&x<v[y])
				{
					v[y]=x;
					pc[y]=pos;
				}
			}
		--i;
		viz[pos]=1;
	}
}

void write()
{
	int i,S=0;
	for (i=1;i<=N;++i)
		S+=v[i];
	printf("%ld\n%ld\n",S,N-1);
	for (i=N;i>1;--i)
		printf("%ld %ld\n",i,pc[i]);
}