using namespace std;
#include <cstdio>

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

nod * G[200002];
int n,t[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;
	t[1]=0;
	int s=0;
	for(int k=1;k<n;++k)
	{
		int cmin=1<<30,imin,jmin;
		for(i=1;i<=n;++i)
			if(t[i]>=0)
				for(nod *p=G[i]; p ; p=p->next)
					if(t[p->vf]==-1)
						if(p->cost < cmin)
							cmin = p->cost,imin=i, jmin=p->vf;
		if(cmin < 1<<30)
			t[jmin]=imin, s+=cmin;
	}
	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;
}