#include <fstream>
#include <algorithm>
#define nm 500000

using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");

int n, m, X[nm], Y[nm], C[nm], INDEX[nm], total;

bool change(int i, int j)
{
	return (C[i] < C[j]);
}

void kruskal()
{
	int conex[nm], s0, s1;
	for(int i = 1; i <= n; i ++)
		conex[i] = i;
	
	for(int c = 0, i = 0; c < n - 1; i ++)
	{
		if(conex[X[INDEX[i]]] != conex[Y[INDEX[i]]])
		{
			s0 = conex[X[INDEX[i]]];
			s1 = conex[Y[INDEX[i]]];
			for(int j = 1; j <= n; j ++)
				if(conex[j] == s0 || conex[j] == s1)
					conex[j] = X[INDEX[i]];
			c ++;
			total += C[INDEX[i]];
		}
		else
			INDEX[i] = -1;
	}
	g << total << '\n' << n - 1 << '\n';
	int c = 0;
	for(int i = 0; i < m, c < n - 1; i ++)
	{
		if(INDEX[i] != -1)
		{
			g << X[INDEX[i]] << ' ' << Y[INDEX[i]] << '\n';
			c ++;
		}
	}
}

int main()
{
	f >> n >> m;
	for(int i = 0; i < m; i ++)
	{
		f >> X[i] >> Y[i] >> C[i];
		INDEX[i] = i;
	}
	sort(INDEX, INDEX + m, change);
	kruskal();
}