#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("apm.in");
ofstream out("apm.out");
#define cin in
#define cout out
#endif // LOCAL

const int nmax = 2e5 + 7;

int parinte[nmax];
int marime[nmax];

int get_tata(int x) {
	if(x == parinte[x]) return x;
	else { // Oportunitatea 1 de optimizare
		return get_tata(parinte[x]);
	}
}

bool Query(int a, int b) {
	int ta = get_tata(a);
	int tb = get_tata(b);

	if(ta == tb) {
		// a si b sunt in acelasi arbore din padure
		return true;
	}
	else {
		// a si b sunt in arbori diferiti
		return false;
	}
}

void Join(int a, int b) {
	int ta = get_tata(a);
	int tb = get_tata(b);

	if(ta == tb) {
		// a si b sunt in acelasi arbore din padure
		return;
	}

	parinte[ta] = tb;
	marime[tb] = marime[ta] + marime[tb]; // Oportunitatea 2 de optimizare
}

vector<pair<int, pair<int, int>>> muchii;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, m; cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, cost; cin >> u >> v >> cost;
		muchii.push_back({cost, {u, v}});
	}

	sort(muchii.begin(), muchii.end()); // sortam a.i. costul sa fie crescator

	// void Join(a, b) -> uneste seturile lui a si al lui b <-> trage o muchie intre arborii lui a si b <-> trage muchia (a, b)
	// bool Query(a, b) -> Adevarat daca si numai daca sunt in acelasi set (arbore) din padure <-> daca exista un drum prin muchiile adaugate de la a la b

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

	int sum = 0;
	vector<pair<int, int>> alese;
	for(auto muchie : muchii) {
		int cost = muchie.first;
		int x = muchie.second.first, y = muchie.second.second;

		if(!Query(x, y)) {
			sum += cost;
			alese.push_back({x, y});

			Join(x, y);
		}
	}

	cout << sum << '\n';
	cout << alese.size() << '\n';
	for(auto muchie : alese) {
		cout << muchie.first << ' ' << muchie.second << '\n';
	}
}