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