# include <fstream>
# include <climits>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int maxn = 10000;

int mc[maxn][maxn],n,m,cost;

void prim(int radacina)
{
	int rad, i, j, min, s[maxn], t[maxn], K;

	rad = radacina;

	for (i = 1; i <= n; i++)
		s[i] = rad;

	s[rad] = 0;
	for (i = 1; i <= n; i++)
		t[i] = 0;

	cost = 0;

	for (K = 1; K <= n - 1; K++)
	{
		min = INT_MAX;
		for (i = 1; i <= n; i++)
			if (s[i])
				if (mc[s[i]][i] < min && mc[s[i]][i])
				{
					min = mc[s[i]][i];
					j = i;
				}
		t[j] = s[j];

		cost =cost + min;

			s[j] = 0;
		for (i = 1; i <= n; i++)
			if (s[i])
				if (!mc[i][s[i]] || mc[i][s[i]]>mc[i][j])
					if (mc[i][j])
						s[i] = j;
	}

	g << cost << "\n";
	g << K << "\n";
	for (i = 1; i <= n; i++)
		if (t[i] != 0)
			g << i << " " << t[i] << "\n";
}

int main()
{
	f >> n >> m;
	int i, j, x, y, z;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			mc[i][j] = INT_MAX;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y >> z;
		mc[x][y] = mc[y][x] = z;
	}
	prim(1);
}