#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m,cc[200005],nr,S,mini,maxi;
struct Muchie
{
	int x, y, c;
}v[400005],sol[200005];
bool cmp(Muchie a, Muchie b)
{
	return a.c < b.c;
}
int main()
{
	int i,j;
	fin >> n >> m;
	for (i = 1; i <= m; i++)
		fin >> v[i].x >> v[i].y >> v[i].c;
	sort(v + 1, v + m + 1, cmp);
	for(i=1;i<=n;i++)
		cc[i] = i;
	for (i = 1; i <= m&&nr<n-1; i++)
	{
		if (cc[v[i].x] != cc[v[i].y])
		{
			S += v[i].c;
			sol[++nr] = v[i];
			mini = min(cc[v[i].x], cc[v[i].y]);
			maxi = max(cc[v[i].x], cc[v[i].y]);
			for (j = 1; j <= n; j++)
				if (cc[j] == maxi) cc[j] = mini;
		}
	}
	fout << S << '\n';
	fout << nr << '\n';
	for (i = 1; i <= nr; i++)
		fout << sol[i].x << ' ' << sol[i].y << '\n';
	return 0;
}