#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 200050
#define MMAX 400050

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

int T[NMAX], M_apm[MMAX], n, m, cst, m_apm;
muchie M[MMAX];

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

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

void citire () {
	
	freopen ("apm.in", "r", stdin);
	
	int i, x, y, c;
	
	scanf ("%d %d", &n, &m);
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d %d", &x, &y, &c);
		M[i].x = x, M[i].y = y, M[i].c = c;
	}
}

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

int 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;
}

void kruskal () {
	
	int i, x, y;
	
	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;
		
		if (!ciclu (x, y)) {
			uneste (x, y);
			cst += M[i].c, m_apm++, M_apm[m_apm] = i;
		}
		
		if (m_apm == n - 1)
			return;
	}
}

void afisare () {
	
	freopen ("apm.out", "w", stdout);
	
	int i;
	
	printf ("%d\n%d\n", cst, m_apm);
	
	for (i = 1; i <= m_apm; i++)
		printf ("%d %d\n", M[ M_apm[i] ].x, M[ M_apm[i] ].y);
}