#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m,nr,S,mini,maxi,tata[200005],h[200005];
struct Muchie
{
	int x, y, c;
}v[400005],sol[200005];
bool cmp(Muchie a, Muchie b)
{
	return a.c < b.c;
}
int Find(int k)
{
	int x = k;
	while (tata[k])
		k = tata[k];
	if (x != k)
	{
		while (tata[x] != k)
		{
			int aux = tata[x];
			tata[x] = k;
			x = aux;
		}
	}
	return k;
}
void Union(int x, int y)
{
	x = Find(x);
	y = Find(y);
	if (h[x] < h[y])
		tata[x] = y;
	else if (h[x] > h[y])
		tata[y] = x;
	else
	{
		tata[x] = y;
		h[y]++;
	}
}
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 <= m&&nr<n-1; i++)
	{
		if (Find(v[i].x) != Find(v[i].y))
		{
			S += v[i].c;
			sol[++nr] = v[i];
			Union(v[i].x, v[i].y);
		}
	}
	fout << S << '\n';
	fout << nr << '\n';
	for (i = 1; i <= nr; i++)
		fout << sol[i].x << ' ' << sol[i].y << '\n';
	return 0;
}