#include <fstream>
#include <algorithm>
#define NM 200001
#define MM 400000
using namespace std;
int n,m,a[NM],v[NM],x[MM],y[MM],c[MM],o[MM],vc,s;
int Root(int i)
{
	while(a[i])
		i=a[i];
	return i;
}
void Unite(int i,int j)
{
	a[Root(i)]=Root(j);
}
bool cmp(int a,int b)
{
	return c[a]<c[b];
}
ifstream fin("apm.in");
ofstream fout("apm.out");
int main()
{
	int i;
	fin>>n>>m;
	for(i=0;i<m;i++)
	{
		fin>>x[i]>>y[i]>>c[i];
		o[i]=i;
	}
	sort(o,o+m,cmp);
	for(i=0;i<m;i++)
		if(Root(x[o[i]])!=Root(y[o[i]]))
		{
			s+=c[o[i]];
			Unite(x[o[i]],y[o[i]]);
			v[vc++]=o[i];
		}
	n--;
	fout<<s<<"\n"<<n<<"\n";
	for(i=0;i<n;i++)
		fout<<x[v[i]]<<" "<<y[v[i]]<<"\n";
	return 0;
}