#include <fstream>
#include <vector>

using namespace std;

#define NMAX 200050
#define INF 0x3f3f3f3f

int H[NMAX], C[NMAX], T[NMAX], poz[NMAX], N, cmin, n, m;
vector < pair <int, int> > G[NMAX], APM;

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

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

void prim () {
	
	int nod, fiu, cst;
	vector < pair <int, int> >::iterator it;
	
	memset (C, INF, sizeof (C));
	
	N++, H[1] = 1, poz[1] = 1;
	while (N) {
		nod = H[1]; poz[nod] = -1;
		
		H[1] = H[N], poz[ H[1] ] = 1, N--;
		down_heap (1);
		
		if (nod != 1) {
			cmin += C[nod];
			APM.push_back (make_pair (T[nod], nod));
		}
		
		for (it = G[nod].begin (); it != G[nod].end (); it++) {
			fiu = it -> first, cst = it -> second;
			
			if (poz[fiu] != -1 && cst < C[fiu]) {
				C[fiu] = cst, T[fiu] = nod;
				
				if (!poz[fiu]) {
					N++, H[N] = fiu, poz[fiu] = N;
					up_heap (N);
				}
				else
					up_heap (poz[fiu]);
			}
		}
	}
}

void up_heap (int k) {
	
	int c = k, t = c >> 1;
	
	while (t > 0 && C[ H[c] ] < C[ H[t] ]) {
		swap (H[c], H[t]);
		poz[ H[c] ] = c, poz[ H[t] ] = t;
		
		c = t, t = c >> 1;
	}
}

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

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

void afisare () {
	
	ofstream g ("apm.out");
	
	vector < pair <int, int> >::iterator it;
	
	g << cmin << "\n" << n - 1 << "\n";
	
	for (it = APM.begin (); it != APM.end (); it++)
		g << it -> first << " " << it -> second << "\n";
	
	g.close ();
}