#include <fstream>
#include <vector>
#include<tuple>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAX_NR_NODES 200000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int parents[MAX_NR_NODES + 1];

int findParent(int node) {
	if (parents[node] < 0) {
		return node;
	}
	return findParent(parents[node]);
}

void unifyDisjointComponents(int parent1, int parent2) {
	if (-parents[parent1] >= -parents[parent2]) {
		parents[parent1] += parents[parent2];
		parents[parent2] = parent1;
	} else {
		parents[parent2] += parents[parent1];
		parents[parent1] = parent2;
	}
}

void printMSTInformation(int minimumSpanningTreeCost, int nrNodes, queue<pair<int,int>>& mstListEdges) {
	fout << minimumSpanningTreeCost << '\n';
	fout << nrNodes - 1 << '\n';
	while (!mstListEdges.empty()) {
		fout << mstListEdges.front().first << ' ' << mstListEdges.front().second << '\n';
		mstListEdges.pop();
	}
}

void kruskalMST(vector<tuple<int, int, int>>& listEdges, int nrNodes) {
	sort(listEdges.begin(), listEdges.end());
	memset(parents, -1, sizeof(parents));
	int minimumSpanningTreeCost = 0, minimumSpanningTreeEdges = nrNodes - 1;
	int idx = 0;
	queue<pair<int, int>> mstListEdges;
	while (minimumSpanningTreeEdges) {
		tuple<int, int, int> edge = listEdges[idx];
		int weight = get<0>(edge);
		int node1 = get<1>(edge);
		int node2 = get<2>(edge);

		int parent1 = findParent(node1);
		int parent2 = findParent(node2);
		if (parent1 != parent2) {
			unifyDisjointComponents(parent1, parent2);
			--minimumSpanningTreeEdges;
			minimumSpanningTreeCost += weight;
			mstListEdges.push({ node1, node2 });
		}
		++idx;
	}
	printMSTInformation(minimumSpanningTreeCost, nrNodes, mstListEdges);
}

int main() {
	int nrNodes, nrEdges;
	fin >> nrNodes >> nrEdges;
	vector<tuple<int, int, int>> listEdges;
	for (int edge = 0; edge < nrEdges; ++edge) {
		int node1, node2, weight;
		fin >> node1 >> node2 >> weight;
		listEdges.push_back(make_tuple(weight, node1, node2));
	}
	kruskalMST(listEdges, nrNodes);
	return 0;
}