#include <fstream>
#include <algorithm>
#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)
{
	if (x == t[x]) return x;
	t[x] = get_anc(t[x]);
}

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

bool comp(muchie x, muchie y)
{
	return (x.c > y.c);
}

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;
	sort(m, m + mu, comp);
	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[m_added[i]].n1 << " " << m[m_added[i]].n2 << "\n";
	return 0;
}