#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

struct muchie { int n1, n2, cst;};

bool cmp (const muchie &a, const muchie &b) { return a.cst<b.cst; }

muchie a[400005];

vector<int> sol;

int t[200005],nr[200005],n,m,s;

void solve()
{
	int i,r1,r2,R;
	
	for (i=1;i<=n;i++)
		nr[i]=1,t[i]=i;
	
	for (i=1;i<=m;i++)
	{
		for (r1=t[a[i].n1];r1!=t[r1];r1=t[r1]);
		for (r2=t[a[i].n2];r2!=t[r2];r2=t[r2]);
		if (r1!=r2)
		{
			if (nr[r1]>nr[r2])
			{
				R=r1;
				t[r2]=R;
				for (r1=a[i].n1;r1!=R;r2=r1,r1=t[r1],t[r2]=R);
				for (r2=a[i].n2;r2!=R;r1=r2,r2=t[r2],t[r1]=R);
			}
			else
			{
				R=r2;t[r1]=R;
				if (nr[r1]==nr[r2])
					nr[r2]++;
				for (r1=a[i].n1;r1!=R;r2=r1,r1=t[r1],t[r2]=R);
				for (r2=a[i].n2;r2!=R;r1=r2,r2=t[r2],t[r1]=R);
			}
			s+=a[i].cst;
			sol.push_back(i);
		}
	}
}
void citire()
{
	int i,x,y,c;
	ifstream f("apm.in");
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		a[i].n1=x;a[i].n2=y;a[i].cst=c;
	}
	sort(a+1,a+m+1,cmp);
}

void afisare()
{
	int i,k;
	ofstream g("apm.out");
	g<<s<<'\n';
	k=sol.size();
	g<<k<<'\n';
	for (i=0;i<k;i++)
		g<<a[sol[i]].n1<<' '<<a[sol[i]].n2<<'\n';
	g.close();
}

int main()
{
	citire();
	solve();
	afisare();
	return 0;
}