#include <iostream>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct MUCHIE
{
	int x,y,cost;
}u[100];

int L[50],m,n;

void citire_muchii()
{
    f>>n>>m;

	for(int i=1 ; i <= m ; i++)
		f>>u[i].x>>u[i].y>>u[i].cost;
}
void sortare()
{
    MUCHIE aux;
	for(int i=1 ; i <= m-1 ; i++)
		for(int j=i+1 ; j <= m ; j++)
			if(u[i].cost > u[j].cost)
			{
			    aux=u[i];
                u[i]=u[j];
                u[j]=aux;
			}
}

void creare_apm()
{
    int k,i,j,v,w,muchii=0,ar[50][2],cost=0;

	for(i=1 ; i <= n ; i++)
        L[i]=i;  //n subarbori disjuncti

	i=1;
	k=0;

	while(k<n-1)
	{
        if(L[u[i].x] != L[u[i].y]) //extremitatile muchiei sunt in subarbori diferiti
		{
			k++;
			cost=cost + u[i].cost;  //adaugam costul muchiei i
			ar[muchii][0]=u[i].x;
			ar[muchii][1]=u[i].y;//adaugam muchia pentru a o afisa mai tarziu
			muchii++;
            v=L[u[i].y];
            w=L[u[i].x];

			for(j=1 ; j <= n ; j++)
				if(L[j]==v)
                    L[j]=w;  //reunim cei doi arbori
		}
		i++; //trecem la urmatoarea muchie
	}

	g<<cost<<endl;
	g<<muchii<<endl;

    for(i=0 ; i < muchii ; i++)
        g<<ar[i][0]<<" "<<ar[i][1]<<endl;
}
int main()
{
    citire_muchii();
	sortare();
	creare_apm();
	return 0;
}