#include <fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int x[400001],y[400001],c[400001],indic[400001],grup[400001],n,m,i,s;
vector <int> v;
int cpfm(int i,int j)
{return c[i]<c[j];

}

int grupa(int i)
{
	if (grup[i] == i) return i;
	grup[i] = grupa(grup[i]);
	return grup[i];
}

void reuniune(int i,int j)
{
	grup[grupa(i)] = grupa(j);
}

int main()
{f>>n>>m;
for(i=1;i<=m;i++)
    {f>>x[i]>>y[i]>>c[i];
    indic[i]=i;}


sort(indic+1,indic+m+1,cpfm);


 	for(int i=1;i<=n;++i)
        grup[i] = i;


	for(int i= 1;i <= m; ++i)
	{
		if (grupa(x[indic[i]]) != grupa(y[indic[i]])){
			s=s+c[indic[i]];
                reuniune(x[indic[i]],y[indic[i]]);
v.push_back(indic[i]);
		}
	}
	g<<s<<'\n';
g<<n-1<<'\n';
  for(i=0;i<n-1;i++)
        g<<x[v[i]]<<" "<<y[v[i]]<<'\n';
    return 0;
}