#include<iostream.h>
#include<fstream.h>
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchii
{
	long a,b,c;
} m[400000];
struct muchii2
{
	long a1,b1;
} A[399999];
long p[200000],h[200000],C,k,mu,n;
void makeset(long u)
{
	p[u]=0;
	h[u]=0;
}
int findset(long u)
{
	if (p[u]==0)
		return u;
	p[u]=findset(p[u]);
	return p[u];
}
void union1(long u, long v)
{
	u=findset(u);
	v=findset(v);
	if (h[u]>h[v])
		p[v]=u;
	else 
	{
		p[u]=v;
		if (h[u]==h[v])
			h[v]++;
	}
}
void sort()
{
	long i,j;
	muchii aux;
	for (i=0;i<mu-1;i++)
		for (j=i+1;j<mu;j++)
			if (m[i].c>m[j].c) 
			{
				aux=m[i];
				m[i]=m[j];
				m[j]=aux;
			}
}
void kruskal()
{
	long i;
	k=0;
	C=0;
	for(i=0;i<n;i++)
		makeset(i);
	sort();
	for (i=0; i<mu;i++)
	{
		if (findset(m[i].a)!=findset(m[i].b))
		{
			A[k].a1=m[i].a;
			A[k].b1=m[i].b;
			k++;
			C=C+m[i].c;
			union1(m[i].a,m[i].b);
			if (k==mu-1)
				break;
		}
	}
}
int main()
{
	long i;
	fin>>n>>mu;
	for (i=0;i<mu;i++)
		fin>>m[i].a>>m[i].b>>m[i].c;
	kruskal();
	fout<<C<<endl<<k<<endl;
	for (i=0;i<k;i++)
		fout<<A[i].a1<<" "<<A[i].b1<<endl;
	return 0;
}