#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 1;

int n, m;
int x, y, c;
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
int t[N];
long long total;
vector<pair<int, int>> ans;

int rad(int nod) {
	if (t[nod] == nod) return nod;

	return t[nod] = rad(t[nod]);
}

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; ++i) {
		t[i] = i;
	}

	while (m--) {
		cin >> x >> y >> c;

		pq.push({ c, x, y });
	}

	while (!pq.empty()) {
		int cost = get<0>(pq.top()), x = get<1>(pq.top()), y = get<2>(pq.top());
		pq.pop();

		int rx = rad(x), ry = rad(y);

		if (rx != ry) {
			t[rx] = t[ry];

			total += cost;
			ans.push_back({ x, y });
		}
	}

	cout << total << '\n';
	cout << ans.size() << '\n';
	for (auto& i : ans) cout << i.first << ' ' << i.second << '\n';

	return 0;
}