// apm.cpp : Defines the entry point for the console application.
//

#include <cstdio>
#include <algorithm>
using namespace std;

int n,m;
struct graf
{
	int e1,e2,c;
};
graf g[400001];
graf h[400001];
int con[200001];
int d[400001];
long long cost=0;
int muchii=1;


void citire()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d %d %d",&g[i].e1,&g[i].e2,&g[i].c);
	for(int i=1;i<=n;i++)
		con[i]=i;
}





void lucru()
{
	int x;
	for(int i=1;i<=m;i++)
		if(con[g[i].e1]!=con[g[i].e2])
		{
			d[muchii]=i;
			cost=cost+g[i].c;
			muchii++;
			x=con[g[i].e1];
			for(int j=1;j<=n;j++)
				if(con[j]==x)
					con[j]=con[g[i].e2];
		}
	muchii--;
}

void scriere()
{
	printf("%lld\n",cost);
	printf("%d\n",muchii);
	for(int i=1;i<=muchii;i++)
		printf("%d %d\n",g[d[i]].e1,g[d[i]].e2);
}

int cmp(const graf &a, const graf &b)
{
	return a.c < b.c;
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	citire();
	sort(g+1,g+1+m,cmp);
	lucru();
	scriere();


	return 0;
}