#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define in "apm.in"
#define out "apm.out"
#define N 200005

struct muchie {
	int x, y, c;
};

vector <muchie> LIST, R;
vector <int> d (N+1, 0);
int n, m, sol, sel;

muchie init (int x, int y, int c)
{
	muchie a;
	a.x = x, a.y = y, a.c = c;
	return a;
}

bool cmp (muchie a, muchie b)
{
	return a.c < b.c;
}

int main ()
{
	ifstream fin (in);
	fin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int x, y, c;
		fin >> x >> y >> c;
		LIST.push_back (init (x, y, c));
	}
	for (int i = 1; i <= n; ++i)
		d[i] = i;
	fin.close();
	sort (LIST.begin(), LIST.end(), cmp);
	for (unsigned i = 0; sel < n - 1; ++i) {
		if (d[LIST[i].x] != d[LIST[i].y]) {
			sel++;
			sol += LIST[i].c;
			R.push_back (LIST[i]);
			int MAX = max (d[LIST[i].x], d[LIST[i].y]);
			int MIN = min (d[LIST[i].x], d[LIST[i].y]);
			for (int j = 1; j <= n; ++j)
				if (d[j] == MAX)
					d[j] = MIN;
		}
	}
	ofstream fout (out);
	fout << sol << "\n" << n - 1 << "\n";
	for (int i = 0; i < n - 1; ++i)
		fout << R[i].x << " " << R[i].y << "\n";
	fout.close();
	return 0;
}