#include <fstream>
#include <vector>
#include<tuple>
#include <algorithm>
#include <queue>
#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]) {
		return node;
	}
	return findParent(parents[node]);
}

void unifyDisjointComponents(int parentNode1, int parentNode2) {
	parents[parentNode2] = parentNode1;
}

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());
	int minimumSpanningTreeCost = 0, minimumSpanningTreeEdges = nrNodes - 1;
	int idx = 0;
	queue<pair<int, int>> mstListEdges;
	while (minimumSpanningTreeEdges > 0) {
		tuple<int, int, int> edge = listEdges[idx++];
		int weight = get<0>(edge);
		int node1 = get<1>(edge);
		int node2 = get<2>(edge);

		int parentNode1 = findParent(node1);
		int parentNode2 = findParent(node2);
		if (parentNode1 != parentNode2) {
			unifyDisjointComponents(parentNode1, parentNode2);
			--minimumSpanningTreeEdges;
			minimumSpanningTreeCost += weight;
			mstListEdges.push({ node1, node2 });
		}
	}
	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;
}