#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>

#define NMAX 200005

int n, m;
typedef std::pair<int, int> Link;
typedef std::pair<Link, int> Edge;
typedef std::vector<Edge> EdgeContainer;

int setTree[NMAX];
// EdgeContainer neighbors[NMAX];

int findSet(int x) {
	int mainRoot = x, nextRoot;
	while (setTree[mainRoot] != mainRoot) {
		mainRoot = setTree[mainRoot];
	}

	// compression
	while (x != setTree[x]) {
		nextRoot = setTree[x];
		setTree[x] = mainRoot;
		x = nextRoot;
	}
	return mainRoot;
}

void uniteSetsOf(int x1, int x2) {
	setTree[findSet(x1)] = setTree[findSet(x2)];
}

class myComp {
public:
	bool operator() (const Edge& a, const Edge& b) const {
		return a.second > b.second;
	}
};

int main () {
	std::ifstream fin("apm.in");
	std::ofstream fout("apm.out");

	int i, x, y, cost;
	fin >> n >> m;

	std::priority_queue<Edge, EdgeContainer, myComp> heap;

	for (i = 1; i <= m; i++) {
		fin >> x >> y >> cost;
		// neighbors[x].push_back(Edge(Link(x, y), cost));
		// neighbors[y].push_back(Edge(Link(y, x), cost));
		heap.push(Edge(Link(y, x), cost));
	}

	for (i = 1; i <= n; i++) {
		setTree[i] = i;
	}

	EdgeContainer apm;
	long long costTotal = 0;

	while (!heap.empty() && (int) apm.size() < n - 1) {
		Edge e = heap.top();
		heap.pop();

		if (findSet(e.first.first) != findSet(e.first.second)) { // different sets
			uniteSetsOf(e.first.first, e.first.second);
			apm.push_back(e);
			costTotal += e.second;
		}
	}

	fout << costTotal << '\n' << n-1 << '\n';
	for (i = 0; i < n - 1; i++) {
		fout << apm[i].first.first << ' ' << apm[i].first.second << '\n';
	}

	return 0;
}