#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200001

using namespace std;

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

struct ceva
{
	int x, y, c;
};

bool cmp(ceva a, ceva b)
{
	return a.c < b.c;
}

int n, m;
ceva a[NMAX];
vector<int> T(NMAX, -1);
vector<pair<int, int>> rez;
int TotalCost;

int GetRoot(int Node)
{
	int aux = Node;
	while (T[Node] > 0)
		Node = T[Node];

	int Root = Node;
	Node = aux;
	while (Node != Root)
	{
		aux = T[Node];
		T[Node] = Root;
		Node = aux;
	}

	return Root;
}

bool Union(int x, int y)
{
	int xRoot = GetRoot(x);
	int yRoot = GetRoot(y);

	if (xRoot == yRoot)
		return false;

	if (T[xRoot] <= T[yRoot])
	{
		T[yRoot] += T[xRoot];
		T[xRoot] = yRoot;
	}
	else
	{
		T[xRoot] += T[yRoot];
		T[yRoot] = xRoot;
	}

	return true;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		cin >> x >> y >> c;
		a[i] = { x, y, c };
	}

	sort(a + 1, a + m + 1, cmp);
	for (int i = 1; i <= m && rez.size() != n; i++)
	{
		int x = a[i].x;
		int y = a[i].y;
		int c = a[i].c;

		if (Union(x, y))
			TotalCost += c, rez.push_back({ x, y });

	}

	cout << TotalCost << '\n' << rez.size() << '\n';
	for (auto x : rez)
		cout << x.first << ' ' << x.second << '\n';

	return 0;
}