#include <bits/stdc++.h>

using namespace std;

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

struct UF {
	vector < int > group;

	UF() {};
	UF(int elNum) : group(elNum) {
		Reset();
	};

	void Reset() {
		for(int i = 0; i < (int)group.size(); ++i) {
			group[i] = i;
		}
	}
	int Find(int x) {
		if(group[x] == x) return x;
		group[x] = Find(group[x]);
		return group[x];
	}
	bool SameGroup(int a, int b) {
		return (Find(a) == Find(b));
	}
	void Join(int a, int b) {
		group[Find(a)] = Find(b);
	}
};
struct APM {
	struct Edge {
		int from, to;
		int cost;
	};

	int nodeNum = 0;
	int totalCost = 0;
	vector < pair < int, int > > road;
	vector < Edge > vEdge;
	UF unionFind;

	APM() {};
	APM(int nodeNum) : nodeNum(nodeNum), road(nodeNum - 1), unionFind(nodeNum) {};

	void AddEdge(int x, int y, int cost) {
		vEdge.push_back({x, y, cost});
	}

	void Solve() {
		sort(vEdge.begin(), vEdge.end(), [&](const Edge &a, const Edge &b) {
			return a.cost < b.cost;
		});

		int roadNum = 0;
		for(int i = 0; i < (int)vEdge.size() && roadNum < nodeNum - 1; ++i) {
			if(unionFind.SameGroup(vEdge[i].from, vEdge[i].to)) continue;
			unionFind.Join(vEdge[i].from, vEdge[i].to);
			road[roadNum++] = {vEdge[i].from, vEdge[i].to};
			totalCost += vEdge[i].cost;
		}
	}
};

int main() {
	int n, m;
	fin >> n >> m;

	APM Kruskal(n);
	for(int i = 0; i < m; ++i) {
		int x, y, cost;
		fin >> x >> y >> cost;
		
		Kruskal.AddEdge(x - 1, y - 1, cost);
	}

	Kruskal.Solve();
	fout << Kruskal.totalCost << "\n" << n - 1 << "\n";
	for(auto x: Kruskal.road) {
		fout << x.first + 1 << " " << x.second + 1 << "\n";
	}
	return 0;
}