#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 200050
#define MMAX 400050

struct {
	int c, y;
} minim[NMAX];

int H[NMAX], poz[NMAX], n, m, n_apm, m_apm, cst_apm, N;
vector < pair <int, int> > G[NMAX], M_apm;

void citire (), up_heap (int), down_heap (int), add_heap (int), delete_heap (int), prim (), afisare ();

int main () {
	
	citire ();
	
	prim ();
	
	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);
		G[x].push_back (make_pair (y, c));
		G[y].push_back (make_pair (x, c));
	}
}

void up_heap (int k) {
	
	int t, c, aux;
	
	c = k, t = c >> 1;
	while (t > 0 && minim[ H[t] ].c > minim[ H[c] ].c) {
		aux = H[t], H[t] = H[c], H[c] = aux;
		poz[ H[c] ] = c, poz[ H[t] ] = t;
		
		c = t, t = c >> 1;
	}
}

void down_heap (int k) {
	
	int t, c, aux;
	
	t = k, c = t << 1;
	if (c < N && minim[ H[c] ].c > minim[ H[c+1] ].c) c++;
	
	while (c <= N && minim[ H[t] ].c > minim[ H[c] ].c) {
		aux = H[t], H[t] = H[c], H[c] = aux;
		poz[ H[c] ] = c, poz[ H[t] ] = t;
		
		t = c, c = t << 1;
		if (c < N && minim[ H[c] ].c > minim[ H[c+1] ].c) c++;
	}
}

void add_heap (int nod) {
	
	N++, H[N] = nod, poz[nod] = N;
	up_heap (N);
}

void delete_heap (int k) {
	
	poz[ H[k] ] = -1, H[k] = H[N], poz[ H[k] ] = k;
	N--;
	down_heap (k);
}

void prim () {
	
	int i, nod, fiu, cst;
	
	n_apm = 1, poz[1] = -1;
	for (i = 0; i < (int) G[1].size (); i++) {
		fiu = G[1][i].first, cst = G[1][i].second;
		minim[fiu].c = cst, minim[fiu].y = 1;
		add_heap (fiu);
	}
	
	while (n_apm < n) {
		nod = H[1];
		delete_heap (1);
		
		n_apm++;
		cst_apm += minim[nod].c;
		m_apm++, M_apm.push_back (make_pair (nod, minim[nod].y));
		
		for (i = 0; i < (int) G[nod].size (); i++) {
			fiu = G[nod][i].first, cst = G[nod][i].second;
			if (!poz[fiu]) {
				minim[fiu].c = cst, minim[fiu].y = nod;
				N++, H[N] = fiu, poz[fiu] = N;
				up_heap (N);
			}
			else if (cst < minim[fiu].c && poz[fiu] != -1) {
				minim[fiu].c = cst, minim[fiu].y = nod;
				up_heap (poz[fiu]);
			}
		}
	}
}

void afisare () {
	
	freopen ("apm.out", "w", stdout);
	
	int i;
	
	printf ("%d\n%d\n", cst_apm, m_apm);
	
	for (i = 0; i < (int) M_apm.size (); i++)
		printf ("%d %d\n", M_apm[i].first, M_apm[i].second);
}