#include <fstream>
#include <algorithm>

#define NMax 400010

using namespace std;

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

struct Edge {
	int n1;
	int n2;
	int cost;
} G[NMax], answ[NMax];

int nodes, edges, disjoint[100010], nE, tCost;

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

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

	return node;
}

int main()
{
	f >> nodes >> edges;
	for (int i = 1; i <= edges; i++)
		f >> G[i].n1 >> G[i].n2 >> G[i].cost;

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

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

	for (int i = 1; i <= edges && nE < edges - 1; i++) {
		int father1 = find_father(G[i].n1);
		int father2 = find_father(G[i].n2);

		if (father1 != father2) {
			nE++;
			answ[nE].n1 = G[i].n1;
			answ[nE].n2 = G[i].n2;
			tCost += G[i].cost;

			if (-disjoint[father1] > -disjoint[father2]) {
				disjoint[father1] += disjoint[father2];
				disjoint[father2] = father1;
			}
			else {
				disjoint[father2] += disjoint[father1];
				disjoint[father1] = father2;
			}
		}
	}

	g << tCost << '\n';
	g << nE << '\n';
	for (int i = 1; i <= nE; i++) {
		g << answ[i].n1 << ' ' << answ[i].n2 << '\n';
	}

	return 0;
}