#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, i, j, k, x, y, c;
vector <int> t, p;
struct muchie
{
	int x, y, m;
};
vector <muchie> G, sol;
int root(int k)
{
	while (k != t[k])
		k = t[k];
	return k;
}
void unificare(int x, int y)
{
	if (p[x] < p[y])
		t[x] = y;
	if (p[x] > p[y])
		t[y] = x;
	if (p[x] == p[y])
	{
		t[y] = x;
		p[x]++;
	}
}
bool comp(muchie a, muchie b)
{
	return a.m > b.m;
}
int main()
{
	fin >> n >> m; G.resize(m + 1); t.resize(n + 1); p.resize(n + 1); sol.resize(n);
	for (i = 1; i <= m; i++)
		fin >> G[i].x >> G[i].y >> G[i].m;
	sort(G.begin() + 1, G.end(), comp);
	for (i = 1; i <= n; i++)
		t[i] = i;
	i = 1;
	while (k < n - 1)
	{
		x = root(G[i].x); y = root(G[i].y);
		if (x != y)
		{
			++k;
			c += G[i].m;
			sol[k] = G[i];
			unificare(x, y);
		}
		++i;
	}
	fout << c << "\n" << n - 1 << "\n";
	for (i = 1; i < n; ++i)
		fout << sol[i].y << " " << sol[i].x << '\n';
	return 0;
}