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

using namespace std;

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

struct muchie{
	int x, y, cost;

	bool operator<(const muchie temp) const {
		if (cost < temp.cost) return true;
		return false;
	}
};

int n, m;
vector<muchie> adj;
vector<int> parent;
vector<int> rang;

int find(int x)
{
	int repX;
	for (repX = x; parent[repX] != repX; repX = parent[repX]);
	int p = repX;
	for (repX = x; parent[repX] != repX; repX = parent[repX])
	{
		parent[repX] = p;
	}
	return p;
}

void marea_unire(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;
	adj.resize(m + 1);
	parent.resize(n + 1);
	rang.resize(n + 1);
	for (int i = 1; i <= m; i++)
	{
		int x, y, cost;
		cin >> x >> y >> cost;
		adj[i] = { x, y, cost };
	}
	for (int i = 1; i <= n; i++)
	{
		parent[i] = i;
	}
	sort(adj.begin() + 1, adj.begin() + m + 1);

	queue<pair<int, int>> q;
	int suma = 0;
	for (int i = 1; i <= m; i++)
	{
		int x = adj[i].x;
		int y = adj[i].y;
		int cost = adj[i].cost;
		if (find(x) == find(y)) continue;
		marea_unire(x, y);
		q.push({ x, y });
		suma += cost;
	}
	cout << suma << '\n' << q.size() << '\n';
	while (!q.empty())
	{
		pair<int, int> aux = q.front();
		cout << aux.first << " " << aux.second << '\n';
		q.pop();
	}
	/*cout << '\n';
	for (int i = 1; i <= m; i++)
	{
		cout << adj[i].x << " " << adj[i].y << " " << adj[i].cost << "\n";
	}*/
}