//kruskal
#include <cstdio>
#define Nmax 200001
#define Mmax 400001

int N, M, i;
int x[Mmax], y[Mmax], c[Mmax];
int cnx[Nmax], rez[Nmax], s;

inline void swap(int &x, int &y) { int tmp = x; x = y; y = tmp; }
int update(int x) { if (!cnx[x]) return x; cnx[x] = update(cnx[x]); return cnx[x]; }
void merge(int x, int y) { cnx[update(y)] = update(x);} 
int query(int x, int y) { return update(x) == update(y); }

void sort(int p, int q)
{
	int st = p, dr = q, m = c[ (st + dr) >> 1];
	while (st < dr)
	{
		while (c[st] < m) ++st;
		while (c[dr] > m) --dr;
		if (st <= dr) swap(x[st],x[dr]), swap(y[st],y[dr]), swap(c[st++],c[dr--]);
	}
	if (p < dr) sort(p,dr);
	if (q > st) sort(st,q);
}

int main()
{
	for ( freopen("apm.in", "r", stdin), scanf("%d %d\n", &N, &M), i = 1; i<=M; ++i ) scanf("%d %d %d\n", x + i, y + i, c + i);
	sort(1,M);
	for (i = 1; i<=M && rez[0]<N-1; ++i)
		if (!query(x[i],y[i]))
		{
			rez[++rez[0]] = i;
			s+=c[i];
			merge(x[i],y[i]);
		}
	for (freopen("apm.out", "w", stdout), printf("%d\n%d\n", s, N-1), i = 1; i<=rez[0]; ++i) printf("%d %d\n", x[rez[i]], y[rez[i]]);
	return 0;
}