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

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct ceva {
	int x, y, cost;

	bool operator<(const ceva& temp) const
	{
		return cost < temp.cost;
	}
};

int n, m;
vector<ceva> muchii;

vector<int> parent;
vector<int> rang;

int Find(int node)
{
	int repNode;
	for (repNode = node; parent[repNode] != repNode; repNode = parent[repNode]);

	return repNode;
}

void Union(int x, int y)
{
	int repX = Find(x);
	int repY = Find(y);

	if (repX == repY)
		return;

	if (rang[repX] > rang[repY]) parent[repY] = repX;
	else if (rang[repX] < rang[repY]) parent[repX] = repY;
	else
	{
		parent[repY] = repX;
		rang[repX]++;
	}
}

int main()
{
	cin >> n >> m;
	muchii.resize(m + 1);
	rang.resize(n + 1, 1);
	parent.resize(n + 1);
	for (int i = 1; i <= n; i++)
		parent[i] = i;

	for (int i = 1; i <= m; i++)
	{
		int x, y, cost;
		cin >> x >> y >> cost;

		muchii[i] = { x, y, cost };
	}

	sort(muchii.begin() + 1, muchii.begin() + m + 1);

	int suma = 0;
	queue<pair<int, int>> q;
	for (int i = 1; i <= m; i++)
	{
		int x = muchii[i].x;
		int y = muchii[i].y;
		int cost = muchii[i].cost;

		if (Find(x) == Find(y))
			continue;

		suma += cost;
		Union(x, y);
		q.push({ x, y });
	}

	cout << suma << '\n' << q.size() << '\n';
	while (!q.empty())
	{
		cout << q.front().first << " " << q.front().second << '\n';
		q.pop();
	}
}