#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;

const int oo=1<<29;
const int N_MAX=200011;

struct pr {
	int x, y, c;
	pr() : x(0), y(0), c(-1) {}
	pr(int _x, int _y, int _c) : x(_x), y(_y), c(_c) {}
	bool operator<(const pr& x) const {return c < x.c;}
};
vector<pr> v, apm;
vector<pr>::const_iterator it, iend;
int f[N_MAX], r[N_MAX];

inline istream& operator>>(istream& in, pr& v) {in>>v.x>>v.y>>v.c; return in;}
inline ostream& operator<<(ostream& out, const pr& v) {out<<v.x<<' '<<v.y; return out;}
int find(int x)
{
	int y, z;
	for(y=x; y != f[y]; y=f[y]);
	for(; x != f[x]; x=z)
	{
		z=f[x];
		f[x]=y;
	}
	return y;
}
inline void Union(int x, int y)
{
	if(r[x] == r[y])
	{
		if(x != y)
			f[x]=y;
		++r[x];
	}
	else r[x]=r[y]=r[x] <= r[y]? r[x] : r[y];
}
int main()
{
	int N, M, i, ok, fx, fy, s=0;
	ifstream in("apm.in");
	ofstream out("apm.out");
	
	in>>N>>M;
	copy(istream_iterator<pr>(in), istream_iterator<pr>(), back_inserter(v));
	sort(v.begin(), v.end());
	for(i=1; i <= N; ++i)
		f[i]=i, r[i]=1;
	for(it=v.begin(), iend=v.end(), ok=1; it < iend && ok < N; ++it)
	{
		fx=find(it->x);
		fy=find(it->y);
		if(fx != fy)
		{
			s+=it->c;
			apm.push_back(*it);
			Union(fx, fy);
			++ok;
		}
	}
	out<<s<<'\n'<<(N-1)<<'\n';
	copy(apm.begin(), apm.end(), ostream_iterator<pr>(out, "\n"));
	return EXIT_SUCCESS;
}