#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct ceva{int x,y,c;};
struct Nod{int x,y;Nod*leg;};
typedef Nod* nod; nod s;
ceva a[400001];
int n,m,viz[200001],finish;

void afisare(){while (s){fout<<s->x<<" "<<s->y<<endl;s=s->leg;}}

void add(int q1, int q2)
{
	nod p=new Nod;
	p->x=q1;
	p->y=q2;
	p->leg=s;
	s=p;
}

bool cmp(ceva q, ceva w){return (q.c<w.c);}
void refresh(int x, int y)
{
	int i;
	if (x==0) swap(x,y);
	for(i=1; i<=n; i++)
		if (viz[i]==x) viz[i]=y;
}

int verificare()
{
	int i;for(i=1; i<n; i++) if (viz[i]!=viz[i+1]) return 0;
	return 1;
}

int main()
{
	int i,s=0,nr=0;
	fin>>n>>m;
	for(i=1; i<=m; i++)
		fin>>a[i].x>>a[i].y>>a[i].c;
	for(i=1; i<=n; i++) viz[i]=i;
	sort(a+1,a+m+1,cmp);
	for(i=1; i<=m and nr<n-1; i++)
	{
		if (viz[a[i].x]!=viz[a[i].y])
		{
			s+=a[i].c;
			refresh(viz[a[i].x], viz[a[i].y]);
			add(a[i].x, a[i].y);
			nr++;//fout<<a[i].x<<" "<<a[i].y<<endl;
		}
		//finish=verificare();
	}
	fout<<s<<endl;
	fout<<nr<<endl;
	afisare();
	return 0;
}