#include <fstream>
#define N 200001
#define M 400001
using namespace std;

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

struct muchie
{
	int n1, n2, c;
}m[M];

int t[N], m_added[M], maddnr;

void init_mult(int n)
{
	for (int i = 0; i < n; i++)
		t[i] = i;
}

int get_anc(int x)
{
	int r;
	for (r = x; t[r] != r; r = t[r]);
	while (t[x] != x)
	{
		int y = t[x];
		t[x] = r;
		x = y;
	}
	return r;
}

void add(int x, int y)
{
	int ax = get_anc(x), ay = get_anc(y);
	t[ay] = ax;
}

int main()
{
	int n, mu, s = 0;
	f >> n >> mu;
	init_mult(n);
	for (int i = 0; i < mu; i++)
		f >> m[i].n1 >> m[i].n2 >> m[i].c;
	for (int i = 0; i < mu; i++)
		for (int j = i + 1; j < mu; j++)
			if (m[i].c > m[j].c)
			{
				muchie aux = m[i];
				m[i] = m[j];
				m[j] = aux;
			}
	for (int i = 0; i < mu; i++)
		if (get_anc(m[i].n1) != get_anc(m[i].n2))
		{
			s += m[i].c;
			add(m[i].n1, m[i].n2);
			m_added[maddnr++] = i;
		}
	g << s << "\n" << maddnr << "\n";
	for (int i = 0; i < maddnr; i++)
		g << m[i].n1 << " " << m[i].n2 << "\n";
	return 0;
}