#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

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

struct arbore
{
	int X,Y,C;
} a[400001];

int N,M,nr=0,v1[400001],v2[400001];

int compara(arbore a,arbore b)
{
	return a.C<b.C;
}
int det(int x)
{
	int aux,r;
	r=x;
	while(v2[r]!=r)
		r=v2[r];
	while(v2[x]!=x)
	{
		aux=v2[x];
		v2[x]=r;
		x=aux;
	}
	return r;
}

int main()
{
	fin>>N>>M;
	for(int i=1;i<=M;i++)
		fin>>a[i].X>>a[i].Y>>a[i].C;
	for(int i=1;i<=N;i++)
		v2[i]=i;
	sort(a+1,a+M+1,compara);
	int m1,m2,cmin=0;
	for(int i=1;i<=M&&nr<N-1;i++)
	{
		m1=det(a[i].X);
		m2=det(a[i].Y);
		if(m1!=m2)
		{
			cmin+=a[i].C;
			v1[++nr]=i;
			v2[m1]=m2;
		}
	}
	fout<<cmin<<"\n"<<nr<<"\n";
	for(int i=1;i<=nr;i++)
		fout<<a[v1[i]].Y<<" "<<a[v1[i]].X<<"\n";
	return 0;
}