#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 2e5 + 5;
const int MMAX = 4e5 + 5;

struct Edge
{
	int x, y, cost;
	bool used;
	Edge()
	{
		this->x = this->y = this->cost = 0;
		this->used = false;
	}
	Edge(const int &x, const int &y, const int &cost, const bool &used)
	{
		this->x = x;
		this->y = y;
		this->cost = cost;
		this->used = used;
	}
	inline bool operator<(const Edge &other) const
	{
		return this->cost < other.cost;
	}
};

int n, m, father[MMAX];
Edge v[MMAX];

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

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

int main()
{
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	fin >> n >> m;
	int x, y, cost;
	for (int i = 1;i <= m;++i)
	{
		fin >> x >> y >> cost;
		v[i] = Edge(x, y, cost, false);
	}
	sort(v + 1, v + m + 1);
	int nrcc = n, costMin = 0;
	for (int i = 1;i <= m && nrcc > 1;++i)
	{
		x = Find(v[i].x);
		y = Find(v[i].y);
		if (x != y)
		{
			v[i].used = true;
			nrcc--;
			costMin += v[i].cost;
			Union(x, y);
		}
	}
	fout << costMin << "\n" << n - nrcc << "\n";
	for (int i = 1;i <= m;++i)
		if (v[i].used == true)
			fout << v[i].x << " " << v[i].y << "\n";
	fin.close();
	fout.close();
	return 0;
}