#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

inline int next_int() {
	int d;
	scanf("%d", &d);
	return d;
}

const int MAX = 1 << 18;
int n, m, a, b, c, A[MAX];

int get(int a) {
	return A[a] == a ? a : (A[a] = get(A[a]));
}

void merge(int a, int b) {
	A[get(a)] = get(b);
}

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	for (int i = 0; i < MAX; i++) {
		A[i] = i;
	}
	int n = next_int();
	int m = next_int();
	vector<pair<int, pair<int, int> > > edges;
	for (int i = 0; i < m; i++) {
		int a = next_int();
		int b = next_int();
		int c = next_int();
		edges.push_back(make_pair(c, make_pair(a, b)));
	}
	sort(edges.begin(), edges.end());
	vector<pair<int, int> > res;
	int ans = 0;
	for (int i = 0; i < m; i++) {
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		int c = edges[i].first;
		if (get(a) != get(b)) {
			merge(a, b);
			ans += c;
			res.push_back(make_pair(a, b));
		}
	}
	printf("%d\n", ans);
	printf("%d\n", int(res.size()));
	for (int i = 0; i < res.size(); i++) {
		printf("%d %d\n", res[i].first, res[i].second);
	}
	return 0;
}