#define DM 400001
#define DN 200001
#include <algorithm>
#include <fstream>
using namespace std;

ifstream fi ("apm.in");
ofstream fo ("apm.out");
int a, b, w, s, n, m, p[DN], c;
pair <int, pair <int, int> > d[DM];
pair <int, int> ras[DN];

int findset(int x)
{
	if (p[x] == x)
		return x;
	return p[x] = findset(p[x]);
}

void mergeset(int x, int y)
{
	p[findset(x)] = findset(y);
}

int main()
{
	fi >> n >> m;
	for (int i = 1; i <= n; ++i)
		p[i] = i;
	for (int i = 1; i <= m; ++i)
		fi >> d[i].second.first >> d[i].second.second >> d[i].first;
	sort(d + 1, d + 1 + m);
	for (int i = 1; i <= m; ++i)
		if (findset(d[i].second.first) != findset(d[i].second.second))
		{
			mergeset(d[i].second.first, d[i].second.second);
			ras[++c] = d[i].second;
			s+=d[i].first;
		}
	fo << s << '\n' << n - 1 << '\n';
	for (int i = 1; i <= c; ++i)
		fo << ras[i].first << ' ' << ras[i].second << '\n';
	return 0;
}