#include <stdio.h> 
#include <vector> 
#include <algorithm> 
#define nmax 200005
#define mmax 400005

using namespace std;

int n, m, ns, sum, t [nmax], a [mmax], b [mmax], c [mmax], ind [mmax];
vector <int> r;

void scan ()
{
	int i;
	scanf ("%d%d", &n, &m);
	for (i=1; i <= m; ++i) scanf ("%d%d%d", &a [i], &b [i], &c [i]);
}

bool comp (int a, int b)
{
	return c [a] < c [b];
}

void init ()
{
	int i;
	for (i=1; i <= n; ++i) t [i]=i;
	for (i=1; i <= m; ++i) ind [i]=i;
	sort (ind+1, ind+1+m, comp);
}

int grup (int nod)
{
	if (t [nod] == nod) 
		return nod;
	return t [nod]=grup (t [nod]);
}

void apm ()
{
	int i, x, y;
	for (i=1; i <= m; ++i) 
	{
		x=grup (a [ind [i]]);
		y=grup (b [ind [i]]);
		if (x != y) 
		{
			t [x]=y;
			++ns;
			sum += c [ind [i]];
			r.push_back (ind [i]);
		}
	}
}

void print ()
{
	vector <int> :: iterator i;
	printf ("%d\n%d\n", sum, ns);
	for (i=r.begin (); i != r.end (); ++i) 
		printf ("%d %d\n", a [*i], b [*i]);
}

int main ()
{
	freopen ("apm.in", "r", stdin);
	freopen ("apm.out", "w", stdout);
	scan ();
	init ();
	apm ();
	print ();
	return 0;
}