#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 quicksort(muchii m[], long left, long right)
{
	long i = left, j = right;
    muchii tmp;
    long pivot;
	srand(time(NULL));
	long p;
	p=rand()%(j-i)+i;
	pivot=m[p].c;
    /* partition */
    while (i <= j) 
	{
		while (m[i].c < pivot)
            i++;
		while (m[j].c > pivot)
            j--;
		if (i <= j) 
		{
			tmp = m[i];
            m[i] = m[j];
            m[j] = tmp;
            i++;
            j--;
        }
    };
    /* recursion */
    if (left < j)
		quicksort(m, left, j);
	if (i < right)
        quicksort(m, i, right);
}
void kruskal()
{
	long i;
	k=0;
	C=0;
	/*for(i=0;i<n;i++)
		makeset(i);*/
	quicksort(m,0,mu-1);
	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;
}