#include <fstream>
#include <vector>
#include <algorithm>

struct Muchie
{
	int a, b, c, v;
	bool operator<(const Muchie& m)
	{ return c < m.c; }
};

std::vector<int> t;
std::vector<Muchie> M;

std::ifstream fin("apm.in");
std::ofstream fout("apm.out");

int Find(int x)
{
	int y, rad;
	rad = x;
	while (t[rad] != 0)
		rad = t[rad];
	while (x != rad)
	{
		y = t[x];
		t[x] = rad;
		x = y;
	}
	return rad;
}

void Union(int x, int y)
{
	t[y] = x;
}

void Kruskal()
{
	t.clear(); M.clear();
	int n, m, x, y, c, cnt;
	fin >> n >> m;
	t.resize(n+1, 0);
	for (; m; m--)
	{
		fin >> x >> y >> c;
		M.push_back({x, y, c, 0});
	}
	std::sort(M.begin(), M.end());
	m = n; c = 0; cnt = 0;
	for (auto it = M.begin(); it != M.end() && m > 1; it++)
	{
		x = Find((*it).a);
		y = Find((*it).b);
		if (x != y)
		{
			c += (*it).c;
			(*it).v = 1;
			cnt++;
			Union(x, y);
			m--;
		}
	}
	fout << c << "\n" << cnt << "\n";
	for (Muchie muchie : M)
		if (muchie.v)
		fout << muchie.a << " " << muchie.b << "\n";
}
int main()
{
	Kruskal();
	return 0;
}