#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int dimn = 200000;
const int dimm = 400000;

struct Edge {
	int x, y, cost;
	Edge() {}
	Edge(int x, int y, int cost) {
		this->x = x;
		this->y = y;
		this->cost = cost;
	}
	bool operator < (const Edge a) const {
		return cost < a.cost;
	}
};

int n, m;
vector<Edge> edges, sol;

int disJoint[dimn];

void initDisJoint(void) {

	for (int i = 0; i <= n; ++i)
		disJoint[i] = -1;

}

int getRoot(int node) {

	int temp = node;
	while (disJoint[node] > 0)
		node = disJoint[node];

	int root = node;
	node = temp;

	while (node != root) {
		temp = disJoint[node];
		disJoint[node] = root;
		node = temp;
	}

	return root;

}

void joinRoots(int x, int y) {

	if (disJoint[x] < disJoint[y]) {
		disJoint[x] -= disJoint[y];
		disJoint[y] = x;
	}
	else {
		disJoint[y] -= disJoint[x];
		disJoint[x] = y;
	}

}

int main() {

	fin >> n >> m;
	
	for (int i = 1; i <= m; ++i) {

		int x, y, cst;
		fin >> x >> y >> cst;

		edges.push_back(Edge(x, y, cst));

	}

	sort(edges.begin(), edges.end());

	initDisJoint();

	int minCost = 0;
	for (int i = 0; i < m; ++i) {

		int x = getRoot(edges[i].x);
		int y = getRoot(edges[i].y);

		if (x == y)
			continue;

		sol.push_back(edges[i]);
		minCost += edges[i].cost;

		if (sol.size() == n - 1)
			break;

		joinRoots(x, y);

	}

	fout << minCost << "\n" << n - 1 << "\n";

	for (int i = 0; i < n - 1; ++i)
		fout << sol[i].x << ' ' << sol[i].y << '\n';

	return 0;

}

//Trust me, I'm the Doctor!