#include <fstream>

#include <vector>

#include <algorithm>

using namespace std;

ifstream fin ("apm.in");

ofstream fout ("apm.out");

struct muchie {

	int x, y, cost;
};

bool cmp (muchie a, muchie b) {

	return a.cost < b.cost;
}

vector<int> T;

int get_root (int node) {

	int aux = node;

	while (T[node] > 0)
		node = T[node];
	
	int root = node;

	node = aux;

	while (node != root) {

		aux = T[node];

		T[node] = root;

		node = aux;
	}

	return root;
}

void join (int x, int y) {

	int root_x = get_root (x), root_y = get_root (y);
	
	if (T[root_x] <= T[root_y]) {

		T[root_x] += T[root_y];

		T[root_y] = root_x;
	}
	else {

		T[root_y] += T[root_x];

		T[root_x] = root_y;
	}
}

int main () {

	int n, m;

	fin >> n >> m;

	vector<muchie> lista_muchii (m + 1);

	for (int i = 1; i <= m; ++i)
		fin >> lista_muchii[i].x >> lista_muchii[i].y >> lista_muchii[i].cost;
	
	T.assign(n + 1, -1);

	sort(lista_muchii.begin() + 1, lista_muchii.begin() + m + 1, cmp);

	int cost = 0;

	vector<pair<int, int>> rez;

	for (int i = 1; i <= m; ++i) {

		int a = lista_muchii[i].x, b = lista_muchii[i].y, c = lista_muchii[i].cost;

		if (get_root (a) != get_root (b)) {

			cost += c;

			rez.push_back({a, b});

			join (a, b);
		}
	}

	fout << cost << '\n' << n - 1 << '\n';

	for (auto x : rez)
		fout << x.first << ' ' << x.second << '\n';
	
	return 0;
}