#include<fstream>
#include<algorithm>
#define NOD 200010
#define MUCHII 400010

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
	int x, y, c, ok;
}a[MUCHII];
int n, m, t[NOD], h[NOD], nr[NOD], s=0, numar=0;

void Citeste()
{
	int i;
	f>>n>>m;
	for (i=1; i<=m; ++i)  f>>a[i].x>>a[i].y>>a[i].c;
	for (i=1; i<=n; ++i) t[i]=-1, h[i]=nr[i]=1;
}

inline bool cmp(muchie q, muchie w)
{
	return q.c<w.c;
}

int tata(int x)
{
	if (t[x]!=-1) return tata(t[x]);
	return x;
}

void APM()
{
	int i, u, v, tu, tv;
	for (i=1; i<=m; ++i)
	{
		u=a[i].x; v=a[i].y;
		tu=tata(u); tv=tata(v);
		if (tu!=tv)
		{
			a[i].ok=1;
			s+=a[i].c; ++numar;
			if (h[tu]==h[tv])
			{
				t[tu]=tv;
				++h[tv];
				nr[tv]+=nr[tu];
				if (nr[tv]==n) break;
			}
			else if (h[tu]>h[tv])
				{
					t[tv]=tu;
					nr[tu]+=nr[tv];
					if (nr[tu]==n) break;
				}	
				else
				{
					t[tu]=tv;
					nr[tv]+=nr[tu];
					if (nr[tv]==n) break;
				}
		}
	}
}

void Scrie()
{
	int i;
	g<<s<<"\n"<<numar<<"\n";
	for (i=1; i<=m; ++i)
		if (a[i].ok) g<<a[i].x<<" "<<a[i].y<<"\n";
}

int main()
{
	Citeste();
	sort(a+1, a+m+1, cmp);
	APM();
	Scrie();
	f.close();
	g.close();
	return 0;
}