#include <fstream>
#include <vector>
#include <algorithm>
#define INF 200099
#define pb push_back
#include <tuple>
using namespace std;
typedef tuple<int, int, int> edge;
struct cmp {
	bool operator()(edge A, edge B) {
		return get<0>(A) < get<0>(B);
	}
};
int n, m, root[INF], cost;
vector < edge > E;
vector < int > sol;
int getroot(int x) {
	if (root[x] != x) {
		root[x] = getroot(root[x]);
	}
	return root[x];
}
void reunion(int x, int y) {
	root[getroot(x)] = getroot(y);
}
void Kruskal() {
	cmp comparator;
	sort(E.begin(), E.end(), comparator);
	for (int i = 1; i <= n; ++i) root[i] = i;
	int i = 0;
	for (auto e : E) {
		int x = get<1>(e), y = get<2>(e);
		int c = get<0>(e);
		if (getroot(x) != getroot(y)) {
			cost += c;
			sol.push_back(i);
			reunion(x, y);
		}
		i++;
	}
}
int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	f >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y, c;
		f >> x >> y >> c;
		E.push_back(edge(c, x, y));
	}
	Kruskal();
	g << cost << '\n';
	g << sol.size() << '\n';
	for (auto i : sol) {
		g << get<1>(E[i]) << ' ' << get<2>(E[i]) << '\n';
	}
	f.close(); g.close();
	return 0;
}