#include <fstream>
#include <algorithm>
#define MAXN 50010
#define MAXM 250010
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

int n,i,j,m,t[MAXN],rang[MAXN],c,cc,k,res[MAXM][2],nres;

int multime(int n)
{
	if(t[n]!=n)
		return multime(t[n]);
	return t[n];
}

void reuneste(int i, int j)
{
	i=multime(i);
	j=multime(j);
	if(i==j)
		return;
	if(rang[i]<rang[j])
		t[i]=j;
	else
		t[j]=i;
	if(rang[i]==rang[j])
		rang[i]++;
}

struct MUCHIE
{
	int i,j,c;
} g[MAXM];

typedef struct CCOMP
{
	int operator() (MUCHIE a, MUCHIE b) 
	{
		return a.c < b.c;
	}
};

int main()
{
	in>>n>>m;
	for(i=1; i<=m; i++)
		in>>g[i].i>>g[i].j>>g[i].c;
	for(i=1; i<=m; i++)
		t[i]=i;
	
	sort(g+1, g+m+1, CCOMP() );
	
	for(k=1; k<=m; k++)
	{
		i=g[k].i;
		j=g[k].j;
		c=g[k].c;
		
		if(multime(i) == multime(j))
			continue;
		reuneste(i,j);
		cc+=c;
		res[++nres][0] = i;
		res[nres][1] = j;
	}
	out<<cc<<'\n'<<nres<<'\n';
	for(i=1; i<=nres; i++)
		out<<res[i][0]<<' '<<res[i][1]<<'\n';
	
	return 0;
}