#include <fstream>
#include <algorithm>

using namespace std;

#define NMAX 200050
#define MMAX 400050

struct muchie {
	int x, y, c;
} M[MMAX], V[MMAX];

int T[NMAX], cmin, n, m;

bool cmp (muchie, muchie), ciclu (int, int);
void uneste (int, int), kruskal (), citire (), afisare ();

int main () {
	
	citire ();
	
	kruskal ();
	
	afisare ();
	
	return 0;
}

bool ciclu (int x, int y) {
	
	while (T[x] > 0) x = T[x];
	
	while (T[y] > 0) y = T[y];
	
	if (x == y) return 1;
	return 0;
}

void uneste (int x, int y) {
	
	while (T[x] > 0) x = T[x];
	
	while (T[y] > 0) y = T[y];
	
	if (-T[x] > -T[y]) T[x] += T[y], T[y] = x;
	else T[y] += T[x], T[x] = y;
}

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

void kruskal () {
	
	int m_apm = 0, i, x, y, c;
	
	memset (T, -1, sizeof (T));
	
	sort (M + 1, M + 1 + m, cmp);
	
	for (i = 1; i <= m; i++) {
		
		x = M[i].x, y = M[i].y, c = M[i].c;
		
		if (!ciclu (x, y)) {
			uneste (x, y);
			m_apm++, V[m_apm].x = x, V[m_apm].y = y;
			cmin += c;
		}
		
		if (m_apm == n - 1)
			return;
	}
}

void citire () {
	
	ifstream f ("apm.in");
	
	int i, x, y, c;
	
	f >> n >> m;
	
	for (i = 1; i <= m; i++) {
		f >> x >> y >> c;
		M[i].x = x, M[i].y = y, M[i].c = c;
	}
	
	f.close ();
}

void afisare () {
	
	ofstream g ("apm.out");
	
	g << cmin << "\n" << n - 1 << "\n";
	
	for (int i = 1; i < n; i++)
		g << V[i].x << " " << V[i].y << "\n";
	
	g.close ();
}