#include <fstream>
#include <algorithm>

#define NMax 200010

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int nodes, nedges, disjoint[NMax], totalCost, answ[NMax];
struct edge {
	int fext;
	int sext;
	int cost;
};
edge edges[400010];

bool cmp(const edge &e1, const edge &e2)
{
	return e1.cost < e2.cost;
}

int findFather(int node)
{
	while (disjoint[node] > 0)
		node = disjoint[node];

	return node;
}

int main()
{
	f >> nodes >> nedges;
	for (int i = 1; i <= nedges; i++)
		f >> edges[i].fext >> edges[i].sext >> edges[i].cost;

	sort(edges + 1, edges + nedges + 1, cmp);

	for (int i = 1; i <= nodes; i++)
		disjoint[i] = -1;

	int crtEdg = 0, apmNodes = 0;
	while (apmNodes < nodes - 1) {
		int n1 = edges[++crtEdg].fext;
		int n2 = edges[crtEdg].sext;
		int cost = edges[crtEdg].cost;

		int set1 = findFather(n1);
		int set2 = findFather(n2);

		if (set1 == set2)
			continue;

		if (-disjoint[set1] > -disjoint[set2]) {
			disjoint[set1] += disjoint[set2];
			disjoint[set2] = set1;
		}
		else {
			disjoint[set2] += disjoint[set1];
			disjoint[set1] = set2;
		}

		totalCost += cost;
		answ[++apmNodes] = crtEdg;
	}

	g << totalCost << "\n" << nodes - 1 << "\n";
	for (int i = 1; i <= nodes - 1; i++)
		g << edges[answ[i]].fext << " " << edges[answ[i]].sext << "\n";

	return 0;
}