#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int N, M;
const int MMAX = 400005;
const int NMAX = 200005;

int set[NMAX];

typedef pair<int, int> muchie;

typedef pair<int, muchie> c_m;

vector<c_m> muchii(MMAX);

int find(int x) {
	if (x != set[x]) {
		set[x] = find(set[x]);
	}
	return set[x];
}

void union1(int x, int y) {
	int px = find(x);
	int py = find(y);

	if (px == py) {
		return;
	}

	set[px] = py;
}

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d %d", &N, &M);

	for (int i = 1; i < N; ++i) {
		set[i] = i;
	}

	for (int i = 0; i < M; ++i) {
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);
		muchii[i] = make_pair(c, make_pair(x, y));
	}

	sort(muchii.begin(), muchii.end());

	vector<muchie> sol;
	int arb_cost = 0;

	for (auto top : muchii) {
		muchie m = top.second;
		int c = top.first;

		if (find(m.first) != find(m.second)) {
			arb_cost += c;
			union1(m.first, m.second);
			sol.push_back(m);
		}
	}

	printf("%d\n%d\n", arb_cost, int(sol.size()));

	for (muchie m : sol) {
		printf("%d %d\n", m.first, m.second);
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}