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

struct graf { int nod, cost; graf * next; } *g[Nmax];
int N, M, i, x, y, z, min = 0x3f3f3f3f, poz,s;
struct muchie { int x, y, c; } h[Mmax],rez[Nmax];
int nrH, nr;
char uz[Nmax];

inline void swap(muchie &a, muchie &b) { muchie tmp = a; a = b; b = tmp; }

void upHeap(int loc)
{
	if (loc == 1) return;
	int tata = loc >> 1;
	if (h[tata].c > h[loc].c) swap(h[tata],h[loc]), upHeap(tata);
}

void downHeap(int loc)
{
	int fiu = loc << 1;
	if (fiu > nrH) return;
	if (fiu+1 <= nrH && h[fiu+1].c < h[fiu].c) ++fiu;
	if (h[loc].c > h[fiu].c) swap(h[loc],h[fiu]), downHeap(fiu);
}

void pushHeap(muchie x)
{
	h[++nrH] = x;
	upHeap(nrH);
}

void popHeap()
{
	swap(h[1],h[nrH--]);
	downHeap(1);
}

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, &y, &z);
		if (z < min) min = z, poz = x;
		graf * q = new graf; q->nod = y; q->cost = z; q->next = g[x]; g[x] = q;
		q = new graf; q->nod = x; q->cost = z; q->next = g[y]; g[y] = q;
	}
	
	uz[poz] = 1;
	for (graf * p = g[poz]; p; p = p->next) pushHeap((muchie){poz,p->nod,p->cost});
	while (nrH && nr < N-1)
	{
		while (uz[h[1].x] && uz[h[1].y]) popHeap();
		rez[++nr] = h[1];
		poz = h[1].x; 
		if (uz[poz]) poz = h[1].y;
		uz[poz] = 1;
		s+=h[1].c;
		popHeap();
		for (graf *p = g[poz]; p; p = p->next) pushHeap((muchie){poz,p->nod,p->cost} );
	}
	for (freopen("apm.out", "w", stdout), printf("%d\n%d\n", s, N-1), i = 1; i<=nr; ++i) printf("%d %d\n", rez[i].x, rez[i].y);
	return 0;
}