#include <fstream>
#include <algorithm>
#define IN "apm.in"
#define OUT "apm.out"
#define MMAX 400015
#define NMAX 200015

using namespace std;

ifstream in(IN);
ofstream out(OUT);

int l[NMAX], vect[NMAX];

struct MUCHIE{ int st, dr, cost;} v[MMAX];

inline bool cmp(MUCHIE a, MUCHIE b)
{
	return (a.cost<b.cost);
}

inline int radacina(int x)
{
	if(l[x]!=x)
		l[x]=radacina(l[x]);
	return l[x];
}

int main()
{
	int n, m, i, cost=0, k, x, y, ind=0;
	in>>n>>m;
	for(i=1; i<=m; ++i)
		in>>v[i].st>>v[i].dr>>v[i].cost;
	sort(v+1, v+1+m, cmp);
	for(i=1; i<=n; ++i)
		l[i]=i;
	for(i=1, k=0; k<n-1 && i<=m; ++i)
	{
		x=radacina(v[i].st);
		y=radacina(v[i].dr);
		if(x!=y)
		{
			++k;
			cost+=v[i].cost;
			vect[++ind]=i;
			l[y]=x;
		}
	}
	out<<cost<<'\n'<<n-1<<'\n';
	for(i=1; i<=ind; ++i)
		out<<v[vect[i]].st<<' '<<v[vect[i]].dr<<'\n';
	in.close();
	out.close();
	return 0;
}