//Kruskal

#include <stdio.h>
#include <string.h>
#include <algorithm>

#define a first
#define b second
#define Dim 200001

using namespace std;

int T[Dim];
char use[2*Dim];

pair<int,pair<int,int> > v[2*Dim];

int main()
{
	int i,cost,M,N,x,y;

	freopen("apm.in","r",stdin);

	scanf("%d%d",&N,&M);
	for(i=1;i<=M;i++) scanf("%d%d%d",&v[i].b.a,&v[i].b.b,&v[i].a);

	sort(v+1,v+M+1);
	memset(use,0,sizeof(use));

	for(i=1;i<=N;i++) T[i]=i;
	cost=0;
	for(i=1;i<=M;i++)
	{
		x=v[i].b.a;
		y=v[i].b.b;
		while(x!=T[x]) x=T[x];
		while(y!=T[y]) y=T[y];

		if(x!=y)
		{
			T[x]=y;
			cost+=v[i].a;
			use[i]=1;
		}
	}

	freopen("apm.out","w",stdout);

	printf("%d\n%d\n",cost,N-1);
	for(i=1;i<=M;i++)
		if(use[i]) printf("%d %d\n",v[i].b.a,v[i].b.b);

	return 0;
}