#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 200050
#define MMAX 400050

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

int M_apm[MMAX], viz[NMAX], n, m, m_apm, cst;
muchie M[MMAX];
vector <int> G[NMAX];

int cmp (muchie, muchie);
void citire (), DFS (int), apm (), afisare ();

int main () {
	
	citire ();
	
	apm ();
	
	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;
}

void DFS (int nod) {
	
	int i, fiu;
	
	viz[nod] = 1;
	for (i = 0; i < (int) G[nod].size (); i++) {
		fiu = G[nod][i];
		if (!viz[fiu])
			DFS (fiu);
	}
}

void apm () {
	
	int i, x, y;
	
	sort (M + 1, M + 1 + m, cmp);
	
	for (i = 1; i <= m; i++) {
		x = M[i].x, y = M[i].y; memset (viz, 0, sizeof (viz));
		DFS (x);
		if (!viz[y]) {
			G[x].push_back (y), G[y].push_back (x);
			
			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);
	}
}